lightoj 1026 Critical Links 割边

缘起

接着【1】中讲述的思想. 来继续验证【1】中我说的求割边的思想. lightoj 1026 Critical Links

分析

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
给出一张无向图G<n,m>，求割边。

【输入】
多样例，第一行是样例数. 每个样例开始给出n(0 ≤ n ≤ 10000) 表示图中顶点的个数. 后面是n行, 每行的格式
是 u (k) v1 v2 ... vk ，表明和u相邻的k个点. 输入保证每个样例中边的数量<=10w

【输出】
参见样例输出

【样例输入】
3

8
0 (1) 1
1 (3) 2 0 3
2 (2) 1 3
3 (3) 1 2 4
4 (1) 3
7 (1) 6
6 (1) 7
5 (0)

0

2
0 (1) 1
1 (1) 0

【样例输出】
Case 1:
3 critical links
0 - 1
3 - 4
6 - 7
Case 2:
0 critical links
Case 3:
1 critical links
0 - 1

【限制】
2s

裸的求割边. 没什么好说的.

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
//#include "stdafx.h"

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
using namespace std;
//#define LOCAL

const int maxn = 10005, maxm = 100005;

struct Edge
{
	int to, id;
	Edge(int to, int id):to(to), id(id){}
};

int n,id,low[maxn],timestamp[maxn],t, top; //id是边的编号, top是割边的数量

vector<Edge> g[maxn];

struct CutEdge  // 割边 a---b
{
	int a,b;
	CutEdge(){}
	CutEdge(int xx, int oo)
	{
		if (xx>oo)
		{
			swap(xx,oo); // 保证 a<b
		}
		a = xx, b = oo;
	}
	bool operator <(CutEdge o)
	{
		return a==o.a?(b<o.b):(a<o.a);
	}
}ans[maxm]; // ans中保存割边

typedef vector<Edge>::iterator vit;

void dfs(int cur, int fa)
{
	timestamp[cur] = low[cur] = ++t;
	for (vit x = g[cur].begin(); x!=g[cur].end(); x++)
	{
		if (!timestamp[x->to])
		{
			dfs(x->to, x->id);
			low[cur] = min(low[cur], low[x->to]);
			if (low[x->to]>timestamp[cur]) // 出现割边 x->to---cur
			{
				ans[top++] = CutEdge(x->to, cur);
			}
		}
		else if (x->id!=fa)
		{
			low[cur] = min(low[cur], timestamp[x->to]);
		}
	}
}

int main() {
#ifdef LOCAL
	freopen("d:\\data.in", "r", stdin);
	//freopen("d:\\my.out", "w", stdout);
#endif
	int kase;
	scanf("%d", &kase);
	for (int i = 1; i<=kase; i++)
	{
		scanf("%d", &n);
		for (int i = 0; i<n; i++)
		{
			g[i].clear();
		}
		id = 0;
		for (int i = 0,x,k,y; i<n;i++)
		{
			scanf("%d (%d)", &x, &k);
			while (k--)
			{
				scanf("%d", &y);
				if (x<y) // 注意, 这里通过只添加 x<y的边保证了添加边的唯一性,这是一种常用的技巧
				{
					g[x].push_back(Edge(y, id)), g[y].push_back(Edge(x, id));
					id++;
				}
			}
		}
		top = 0;
		memset(low, 0, sizeof(low));
		memset(timestamp, 0, sizeof(timestamp)); // 放到for循环里面去了, wa到吐~
		for (int i = 0; i<n; i++) // 无向图未必连通
		{
			if (!timestamp[i])
			{
				t = 0;
				dfs(i, -1);
			}
		}
		sort(ans, ans+top);
		printf("Case %d:\n",i);
		printf("%d critical links\n", top);
		for (int i = 0; i<top; i++)
		{
			printf("%d - %d\n", ans[i].a, ans[i].b);
		}
	}
	return 0;
}

ac情况

Status Accepted
Time 208ms
Memory 6216kB
Length 1922
Lang C++
Submitted 2019-09-10 18:29:07
Shared
RemoteRunId 1577738

这里多说一句，看一下下面的数据（有重边，而因为本题仅仅是求割边，不涉及bcc，正如【1】所言, 只需要判断一下出现割边就可以了）

1
2
3
4
5
6
1
3
0 (3) 1 2 2
1 (1) 0
2 (4) 0 0 3 3
3 (2) 2 2

我的程序得出的是正确的

1
2
3
Case 1:
1 critical links
0 - 1

但是网上大部分ac程序得到的却是错误的

1
2
3
4
5
Case 1:
3 critical links
0 - 1
0 - 2
2 - 3

究其根本，是因为他们的tarjan算法的第二个参数不是来边的编号（id），而是父节点. 而这是不正确的~

我的模板很棒!!! 我真正想清楚了里面的道理~

参考

【1】https://yfsyfs.github.io/2019/09/10/poj-3352-Road-Construction-%E4%B8%8D%E5%B8%A6%E9%87%8D%E8%BE%B9%E7%9A%84%E8%BE%B9bcc/