【模板】Tarjan 求强连通分量


题目链接:Luogu P1726 上白泽慧音

代码:

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
#include <cstdio>
#include <stack>
#include <vector>
#include <algorithm>

struct Point {
int head, dfn, low;
bool instack;

Point() : head(0), dfn(0), low(0), instack(false) {}
} pt[5005];
struct Path {
int next, to;

Path(int n = 0, int t = 0) : next(n), to(t) {}
} ph[100005];

std::vector<int> ans[5005];
std::stack<int> s;
int n, m, ptr, cnt;

void setPath(int u, int v) {
ph[++ptr] = Path(pt[u].head, v), pt[u].head = ptr;
}

void dfs(int p) {
pt[p].dfn = pt[p].low = ++ptr;
s.push(p), pt[p].instack = true;
for (int i = pt[p].head; i; i = ph[i].next) {
int x = ph[i].to;
if (!pt[x].dfn)
dfs(x), pt[p].low = std::min(pt[p].low, pt[x].low);
else if (pt[x].instack)
pt[p].low = std::min(pt[p].low, pt[x].dfn);
}
if (pt[p].low == pt[p].dfn) {
int temp; cnt++;
do {
temp = s.top();
s.pop();
pt[temp].instack = false;
ans[cnt].push_back(temp);
} while (temp != p);
}
}

void Tarjan() {
ptr = 0;
for (int i = 1; i <= n; ++i)
if (!pt[i].dfn)
dfs(i);
}

int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= m; ++i) {
int u, v, k;
scanf("%d %d %d", &u, &v, &k);
setPath(u, v);
if (k == 2)
setPath(v, u);
}
Tarjan();
int temp = 0;
for (int i = 1; i <= cnt; ++i)
std::sort(ans[i].begin(), ans[i].end());
for (int i = 1; i <= cnt; ++i) {
if (ans[i].size() > ans[temp].size())
temp = i;
else if (ans[i].size() == ans[temp].size() && ans[i][0] < ans[temp][0])
temp = i;
}
printf("%d\n", ans[temp].size());
for (unsigned int i = 0; i < ans[temp].size(); ++i)
printf("%d ", ans[temp][i]);
putchar('\n');
return 0;
}

 评论