「Note」Tarjan

Posted on Edited on In

一些有用的模板

割点割边

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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5005;

int n, m, tot, bans, pans, dfn[MAXN], low[MAXN], root;
vector<int> G[MAXN];
bool b[MAXN][MAXN], p[MAXN];

void tarjan (int u, int fa) {
	dfn[u] = low[u] = ++tot;
	int cnt = 0;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (!dfn[v]) {	
			tarjan (v, u);
			low[u] = min (low[u], low[v]);
			if (low[v] > dfn[u]) {
				if (b[u][v] || b[v][u]) continue;
				b[u][v] = b[v][u] = 1;
				bans++;
			} 
			if (low[v] >= dfn[u]) {
				cnt++;
				if ((cnt <= 1 && u == root) || p[u]) continue;
				p[u] = 1;
				pans++;
			}
		} else if (v != fa) {
			low[u] = min (low[u], dfn[v]);
		}
	}
}

int main () {
	scanf ("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf ("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) {
		root = i;
		tarjan (i, 0);
	}
	printf ("%d\n%d\n", pans, bans);
	return 0;
}

双连通分量

点

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
#include <stack>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 100005;

int n, m, dfn[MAXN], low[MAXN], tot, cnt;
vector<int> G[MAXN];

stack<pair<int, int> > s;
vector<pair<int, int> > dcc[MAXN];

void tarjan (int u, int fa) {
	dfn[u] = low[u] = ++tot;
	int flag = 0;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (!dfn[v]) {
			s.push(make_pair (u, v));
			tarjan (v, u);
			low[u] = min (low[u], low[v]);
			if (low[v] >= dfn[u]) {
				cnt++;
				pair<int, int> y;
				do {
					y = s.top();
					s.pop();
					dcc[cnt].push_back(make_pair (min (y.first, y.second), max (y.first, y.second)));
				} while (y.first != u || y.second != v);
			}
		} else if (v != fa) {
			low[u] = min (low[u], dfn[v]);
			if (dfn[u] >= dfn[v]) {
				s.push(make_pair (u, v));
			}
		}
	}
}

bool check (int x, int y) {
	for (int i = 0; i < dcc[x].size(); i++) {
		if (dcc[x][i] < dcc[y][i]) return 1;
		if (dcc[x][i] > dcc[y][i]) return 0;
	}
	return 1;
}

int main () {
	scanf ("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf ("%d %d", &u, &v);
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) {
		tarjan (i, 0);
	}
	int id = 0;
	for (int i = 1; i <= cnt; i++) {
		sort (dcc[i].begin(), dcc[i].end());
		if (dcc[i].size() > dcc[id].size()) {
			id = i;
		} else if (dcc[i].size() == dcc[id].size() && check (i, id)) {
			id = i;
		}
	}
	printf ("%d\n%d\n", cnt, dcc[id].size());
	for (int i = 0; i < dcc[id].size(); i++) {
		printf ("%d %d\n", dcc[id][i].first, dcc[id][i].second);
	} 
	return 0;
}

边

dfs
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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5005;

int n, m, tot, dfn[MAXN], low[MAXN], root, ans, dcc, deg[MAXN];
vector<int> G[MAXN];
bool b[MAXN][MAXN], p[MAXN][MAXN];
int vis[MAXN];

void tarjan (int u, int fa) {
	dfn[u] = low[u] = ++tot;
	int cnt = 0;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (!dfn[v]) {	
			tarjan (v, u);
			low[u] = min (low[u], low[v]);
			if (low[v] > dfn[u]) {
				if (b[u][v] || b[v][u]) continue;
				b[u][v] = b[v][u] = 1;
			} 
		} else if (v != fa) {
			low[u] = min (low[u], dfn[v]);
		}
	}
}

void dfs (int u) {
	vis[u] = dcc;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (vis[v] || b[u][v]) continue;
		dfs (v);
	}
}

int main () {
	scanf ("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf ("%d %d", &u, &v);
		if (p[u][v] || p[v][u]) continue;
		p[u][v] = p[v][u] = 1;
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) {
		tarjan (i, 0);
	}
	for (int i = 1; i <= n; i++) if (!vis[i]) {
		dcc++;
		dfs (i);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			int v = G[i][j];
			if (vis[i] != vis[v]) {
				deg[vis[v]]++;
			}
		}
	}
	for (int i = 1; i <= dcc; i++) {
		if (deg[i] == 1) ans++;
	} 
	printf ("%d\n", (ans + 1) / 2);
	return 0;
}

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
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int MAXN = 5005;

int n, m, tot, dfn[MAXN], low[MAXN], root, ans, dcc, deg[MAXN];
vector<int> G[MAXN];
bool b[MAXN][MAXN], p[MAXN][MAXN];
int vis[MAXN], s[MAXN], top;

void tarjan (int u, int fa) {
	dfn[u] = low[u] = ++tot;
	s[++top] = u;
	int cnt = 0;
	for (int i = 0; i < G[u].size(); i++) {
		int v = G[u][i];
		if (!dfn[v]) {	
			tarjan (v, u);
			low[u] = min (low[u], low[v]);
		} else if (v != fa) {
			low[u] = min (low[u], dfn[v]);
		}
	}
	if (low[u] == dfn[u]) {
		int v;
		dcc++;
		do {
			v = s[top--];
			vis[v] = dcc;
		} while (v != u);
	}
}

int main () {
	scanf ("%d %d", &n, &m);
	for (int i = 1, u, v; i <= m; i++) {
		scanf ("%d %d", &u, &v);
		if (p[u][v] || p[v][u]) continue;
		p[u][v] = p[v][u] = 1;
		G[u].push_back(v), G[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) if (!dfn[i]) {
		tarjan (i, 0);
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < G[i].size(); j++) {
			int v = G[i][j];
			if (vis[i] != vis[v]) {
				deg[vis[v]]++;
			}
		}
	}
	for (int i = 1; i <= dcc; i++) {
		if (deg[i] == 1) ans++;
	} 
	printf ("%d\n", (ans + 1) / 2);
	return 0;
}
The End
「Ô mon âme, n'aspire pas à la vie immortelle, mais épuise le champ du possible.」