传说中的模板题。
Tarjan算法求割点。
Tarjan算法是求割点算法里边一种十分易于理解的算法。我们知道一个无向图在dfs的过程中会产生一棵生成树，剩下的弦必然不会跨越子树，所以我们通过一遍dfs就能记录下一个点能够返回的它最早的祖先的编号。
对于某个点，如果它以及它的子孙结点不能返回它祖先的结点，那么这个点很明显就是割点。
网上的很多题解都没有讲清楚这题什么意思，而这题的输入也十分的坑爹，再加上我是用VC写的。于是一次CE、一次RE、第三次AC（←虽然代码本身没问题）。
这份代码在图论题目里是十分有代表性的。
题目的意思就是简单的让你求割点的数目。
输入的第一个数字代表点的个数。
然后的几行里面，每行的第一个数字代表第n个点，它们联通到之后的数字的点上。
如果第一个数字为0，代表这组数据结束了。
如果点的个数为0，表示输入结束了。
对于上面这组数据，表示有5个点，其中第5个点连接到第1、2、3、4个点。
这就是坑了我很久的地方。。。。
下面是我的AC代码。
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
| #include <iostream>
#include <vector>
#include <sstream>
#include <string>
#include <algorithm>
#include <cstring>
using namespace std;
struct info{
int len;
int dclock;
int *cut;
int *low;
int *dfn;
info(int n){
len = n;
dclock = 1;
cut = new int[n];
low = new int[n];
dfn = new int[n];
memset(cut, 0, sizeof(int)*len);
memset(dfn, -1, sizeof(int)*len);
}
~info(){
delete[] cut;
delete[] low;
delete[] dfn;
}
};
void dfs(info &tree, vector< vector<int> > &map, int u, int fa){
int son = 0;
tree.dfn[u] = tree.low[u] = tree.dclock++;
for (int i = 0; i < map[u].size(); i++){
int v = map[u][i];
if (tree.dfn[v]<0){
dfs(tree, map, v, u);
son++;
tree.low[u] = min(tree.low[u], tree.low[v]);
if ((fa < 0 && son > 1) (fa >= 0 && tree.low[v] >= tree.dfn[u]))
tree.cut[u] = 1;
}
else if (tree.low[u] > tree.low[v] && v != fa){
tree.low[u] = min(tree.low[u], tree.dfn[v]);
}
}
}
int solve(int n){
vector<vector<int>> map;
map.resize(n);
int s, u;
while (1){
string temp;
getline(cin, temp);
istringstream buf(temp);
buf >> s;
if (s == 0) break;
while (buf >> u){
map[s - 1].push_back(u - 1);
map[u - 1].push_back(s - 1);
}
}
info tree(n);
for (int i = 0; i < n; i++){
if (map[i].size()>0){
dfs(tree, map, i, -1);
break;
}
}
int cnt = 0;
for (int i = 0; i < n; i++){
if (tree.cut[i] == 1)
cnt++;
}
return cnt;
}
int main(int agrc, char *agrv[]){
int n;
while (cin >> n, n){
cout << solve(n) << endl;
}
}
|