今天我刷题了吗
搜索文档…
Tarjan 算法
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(2e4 + 10);
10
const int maxm(2e5 + 10);
11
int ecnt, head[maxn];
12
int tim, dfn[maxn], low[maxn];
13
int ccnt;
14
bool cut[maxn];
15
16
struct edge {
17
int to, nxt;
18
} edges[maxm];
19
20
template<typename T = int>
21
inline const T read()
22
{
23
T x = 0, f = 1;
24
char ch = getchar();
25
while (ch < '0' || ch > '9') {
26
if (ch == '-') f = -1;
27
ch = getchar();
28
}
29
while (ch >= '0' && ch <= '9') {
30
x = (x << 3) + (x << 1) + ch - '0';
31
ch = getchar();
32
}
33
return x * f;
34
}
35
36
template<typename T>
37
inline void write(T x, bool ln)
38
{
39
if (x < 0) {
40
putchar('-');
41
x = -x;
42
}
43
if (x > 9) write(x / 10, false);
44
putchar(x % 10 + '0');
45
if (ln) putchar(10);
46
}
47
48
void addEdge(int u, int v)
49
{
50
edges[ecnt].to = v;
51
edges[ecnt].nxt = head[u];
52
head[u] = ecnt++;
53
}
54
55
void tarjan(int cur, int pre)
56
{
57
int child = 0;
58
dfn[cur] = low[cur] = ++tim;
59
for (int i = head[cur]; compl i; i = edges[i].nxt) {
60
int nxt = edges[i].to;
61
if (not dfn[nxt]) {
62
++child;
63
tarjan(nxt, cur);
64
low[cur] = min(low[cur], low[nxt]);
65
if (pre not_eq cur and low[nxt] >= dfn[cur] and not cut[cur]) {
66
++ccnt;
67
cut[cur] = true;
68
}
69
} else if (nxt not_eq pre) {
70
low[cur] = min(low[cur], dfn[nxt]);
71
}
72
}
73
if (pre == cur and child >= 2) {
74
++ccnt;
75
cut[cur] = true;
76
}
77
}
78
79
int main()
80
{
81
#ifdef ONLINE_JUDGE
82
#else
83
freopen("input.txt", "r", stdin);
84
#endif
85
ios::sync_with_stdio(false);
86
memset(head, -1, sizeof head);
87
int n = read(), m = read();
88
while (m--) {
89
int u = read(), v = read();
90
addEdge(u, v);
91
addEdge(v, u);
92
}
93
for (int i = 1; i <= n; ++i) {
94
if (not dfn[i]) {
95
tarjan(i, i);
96
}
97
}
98
write(ccnt, true);
99
for (int i = 1; i <= n; ++i) {
100
if (cut[i]) {
101
write(i, false);
102
putchar(32);
103
}
104
}
105
return 0;
106
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(1e4 + 10);
10
const int maxm(2e5 + 10);
11
int ecnt, head[maxn], shead[maxn];
12
int tim, dfn[maxn], low[maxn];
13
int scnt, scc[maxn], siz[maxn];
14
int w[maxn], sum[maxn], deg[maxn];
15
bool vis[maxn];
16
stack<int> st;
17
18
struct edge {
19
int to, nxt;
20
} edges[maxm];
21
22
template<typename T = int>
23
inline const T read()
24
{
25
T x = 0, f = 1;
26
char ch = getchar();
27
while (ch < '0' || ch > '9') {
28
if (ch == '-') f = -1;
29
ch = getchar();
30
}
31
while (ch >= '0' && ch <= '9') {
32
x = (x << 3) + (x << 1) + ch - '0';
33
ch = getchar();
34
}
35
return x * f;
36
}
37
38
template<typename T>
39
inline void write(T x, bool ln)
40
{
41
if (x < 0) {
42
putchar('-');
43
x = -x;
44
}
45
if (x > 9) write(x / 10, false);
46
putchar(x % 10 + '0');
47
if (ln) putchar(10);
48
}
49
50
void addEdge(int u, int v, bool s = false)
51
{
52
edges[ecnt].to = v;
53
if (s) {
54
edges[ecnt].nxt = shead[u];
55
shead[u] = ecnt++;
56
} else {
57
edges[ecnt].nxt = head[u];
58
head[u] = ecnt++;
59
}
60
}
61
62
void tarjan(int u)
63
{
64
dfn[u] = low[u] = ++tim;
65
st.push(u);
66
vis[u] = true;
67
for (int i = head[u]; compl i; i = edges[i].nxt) {
68
int v = edges[i].to;
69
if (not dfn[v]) {
70
tarjan(v);
71
low[u] = min(low[u], low[v]);
72
} else if (vis[v]) {
73
low[u] = min(low[u], dfn[v]);
74
}
75
}
76
if (dfn[u] == low[u]) {
77
++scnt;
78
int v = 0;
79
do {
80
v = st.top();
81
st.pop();
82
vis[v] = false;
83
scc[v] = scnt;
84
++siz[scnt];
85
sum[scnt] += w[v];
86
} while (v not_eq u);
87
}
88
}
89
90
int dfs(int u)
91
{
92
int mx = 0;
93
for (int i = shead[u]; compl i; i = edges[i].nxt) {
94
int v = edges[i].to;
95
mx = max(mx, dfs(v));
96
}
97
return sum[u] + mx;
98
}
99
100
int main()
101
{
102
#ifdef ONLINE_JUDGE
103
#else
104
freopen("input.txt", "r", stdin);
105
#endif
106
memset(head, -1, sizeof head);
107
memset(shead, -1, sizeof shead);
108
int n = read(), m = read();
109
for (int i = 1; i <= n; ++i) {
110
w[i] = read();
111
}
112
while (m--) {
113
int u = read(), v = read();
114
addEdge(u, v);
115
}
116
for (int i = 1; i <= n; ++i) {
117
if (not dfn[i]) {
118
tarjan(i);
119
}
120
}
121
for (int u = 1; u <= n; ++u) {
122
for (int i = head[u]; compl i; i = edges[i].nxt) {
123
int v = edges[i].to;
124
int a = scc[u], b = scc[v];
125
if (a not_eq b) {
126
addEdge(a, b, true);
127
++deg[b];
128
}
129
}
130
}
131
int res = 0;
132
for (int i = 1; i <= scnt; ++i) {
133
if (not deg[i]) {
134
res = max(res, dfs(i));
135
}
136
}
137
write(res, true);
138
return 0;
139
}
Copied!
1
#include <bits/stdc++.h>
2
3
using namespace std;
4
using ll = long long;
5
using p = pair<int, int>;
6
const double pi(acos(-1));
7
const int inf(0x3f3f3f3f);
8
const int mod(1e9 + 7);
9
const int maxn(2e6 + 10);
10
const int maxm(2e6 + 10);
11
int ecnt, head[maxn];
12
int tim, dfn[maxn], low[maxn];
13
int scnt, id[maxn];
14
bool vis[maxn];
15
stack<int> st;
16
17
struct edge {
18
int to, nxt;
19
} edges[maxm];
20
21
template<typename T = int>
22
inline const T read()
23
{
24
T x = 0, f = 1;
25
char ch = getchar();
26
while (ch < '0' || ch > '9') {
27
if (ch == '-') f = -1;
28
ch = getchar();
29
}
30
while (ch >= '0' && ch <= '9') {
31
x = (x << 3) + (x << 1) + ch - '0';
32
ch = getchar();
33
}
34
return x * f;
35
}
36
37
template<typename T>
38
inline void write(T x, char c = false)
39
{
40
if (x < 0) {
41
putchar('-');
42
x = -x;
43
}
44
if (x > 9) write(x / 10, false);
45
putchar(x % 10 + '0');
46
if (c) putchar(c);
47
}
48
49
void addEdge(int u, int v)
50
{
51
edges[ecnt].to = v;
52
edges[ecnt].nxt = head[u];
53
head[u] = ecnt++;
54
}
55
56
void tarjan(int u)
57
{
58
dfn[u] = low[u] = ++tim;
59
st.push(u);
60
vis[u] = true;
61
for (int i = head[u]; compl i; i = edges[i].nxt) {
62
int v = edges[i].to;
63
if (not dfn[v]) {
64
tarjan(v);
65
low[u] = min(low[u], low[v]);
66
} else if (vis[v]) {
67
low[u] = min(low[u], dfn[v]);
68
}
69
}
70
if (dfn[u] == low[u]) {
71
int v = -1;
72
++scnt;
73
do {
74
v = st.top();
75
st.pop();
76
vis[v] = false;
77
id[v] = scnt;
78
} while (u not_eq v);
79
}
80
}
81
82
int main()
83
{
84
#ifdef ONLINE_JUDGE
85
#else
86
freopen("input.txt", "r", stdin);
87
#endif
88
int n = read(), m = read();
89
memset(head, -1, sizeof head);
90
while (m--) {
91
int u = read() - 1, a = read(), v = read() - 1, b = read();
92
addEdge(u * 2 + not a, v * 2 + b);
93
addEdge(v * 2 + not b, u * 2 + a);
94
}
95
for (int i = 0; i < n * 2; ++i) {
96
if (not dfn[i]) {
97
tarjan(i);
98
}
99
}
100
bool flag = false;
101
for (int i = 0; i < n; ++i) {
102
if (id[i * 2] == id[i * 2 + 1]) {
103
flag = true;
104
break;
105
}
106
}
107
if (flag) {
108
puts("IMPOSSIBLE");
109
} else {
110
puts("POSSIBLE");
111
for (int i = 0; i < n; ++i) {
112
if (id[i * 2] < id[i * 2 + 1]) {
113
write(0, ' ');
114
} else {
115
write(1, ' ');
116
}
117
}
118
}
119
return 0;
120
}
Copied!
最近更新 1yr ago
复制链接