08月
31

UVA-796 Critical Links

发表于 • 本文总阅读数 次
字数统计: 389

题目

  https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=737

题意

  给出一张无向图，求图的割边。

题目解析

  大致的思路和求图的割点类似，用tarjan算法解决。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define min(a, b) (a < b) ? a : b

const int MAX_N = 1000 + 10;

typedef struct node
{
	int b;
	int next;
} node;

typedef struct edge
{
	int a, b;
} edge;

int cmp(edge a, edge b)
{
	if(a.a != b.a)
	{
		return a.a < b.a;
	}
	else
	{
		return a.b < b.b;
	}
}

int n, bn;
node e[2 * MAX_N * MAX_N];
edge bridge[MAX_N];
int head[MAX_N];
int vis[MAX_N], v_ind;
int low[MAX_N];

void tarjan(int v, int pre)
{
	int i, b;

	vis[v] = v_ind;
	low[v] = v_ind;
	v_ind++;
	for(i = head[v]; i != -1; i = e[i].next)
	{
		b = e[i].b;
		if(vis[b] == 0)
		{
			tarjan(b, v);
			low[v] = min(low[v], low[b]);
			if(low[b] > vis[v])
			{
				if(v < b)
				{
					bridge[bn].a = v;
					bridge[bn].b = b;
				}
				else
				{
					bridge[bn].a = b;
					bridge[bn].b = v;
				}
				bn++;
			}
		}
		else if(b != pre)
		{
			low[v] = min(low[v], vis[b]);
		}
	}
}

int main()
{
	int a, k, b;
	int i, j, en;

	while(scanf("%d", &n) != EOF)
	{
		memset(head, -1, sizeof(head));
		en = 0;
		for(i = 0; i < n; i++)
		{
			scanf("%d (%d)", &a, &k);
			for(j = 0; j < k; j++)
			{
				scanf("%d", &b);
				e[en].b = b;
				e[en].next = head[a];
				head[a] = en;
				en++;
			}
		}
		bn = 0;
		v_ind = 1;
		memset(vis, 0, sizeof(vis));
		for(i = 0; i < n; i++)
		{
			if(vis[i] == 0)
			{
				tarjan(i, i);
			}
		}
		
		std::sort(bridge, bridge + bn, cmp);
		printf("%d critical links\n", bn);
		for(i = 0; i < bn; i++)
		{
			printf("%d - %d\n", bridge[i].a, bridge[i].b);
		}
		printf("\n");
	}
	return 0;
}
分享到：
0%