UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#214854#2683. Tourist Reformlinzhiyi1001334ms8804kbC++1014b2024-11-22 19:38:512024-11-22 23:12:41

answer

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = 2e5 + 10;
int n, m, tot = 1, nbs[N], ans;
int dfn[N], low[N], t, cnt, s[N];
stack<int> st; bool in_st[N];
struct edge
{
	int ed, next;
}b[M << 1];
void add(int u, int v)
{
	b[++ tot] = {v, nbs[u]}, nbs[u] = tot;
}
void tarjan(int x, int last)
{
	dfn[x] = low[x] = ++ t;
	st.push(x), in_st[x] = 1;
	for (int i = nbs[x]; i; i = b[i].next)
	{
		int j = b[i].ed;
		if (j == last) continue;
		if (!dfn[j]) tarjan(j, x), low[x] = min(low[x], low[j]);
		else if (in_st[j]) low[x] = min(low[x], low[j]);
	}
	if (dfn[x] == low[x])
	{
		int y;
		++ cnt;
		do
		{
			y = st.top();
			st.pop();
			in_st[y] = 0;
			s[cnt] ++;
		} while (x != y);
	}
}
int main()
{
	cin >> n >> m;
	for (int i = 1, u, v; i <= m; i ++ )
		cin >> u >> v, add(u, v), add(v, u);
	for (int i = 1; i <= n; i ++ )
		if (!dfn[i]) tarjan(i, 0);
	for (int i = 1; i <= cnt; i ++ )
		ans = max(ans, s[i]);
	cout << ans;
	return 0;
}

详细

小提示:点击横条可展开更详细的信息

Test #1:

score: 5
Accepted
time: 1ms
memory: 1268kb

input:

20 30
18 7
17 16
13 5
19 17
4 7
15 7
3 4
19 9
18 19
12 8
9 2
20 10
1 13
16 10
7 3
1 10
17 6
9 8
6 15...

output:

18

result:

ok single line: '18'

Test #2:

score: 5
Accepted
time: 0ms
memory: 1264kb

input:

20 30
16 15
4 17
20 4
18 7
7 4
4 1
19 20
15 19
7 6
18 1
9 8
8 20
19 8
9 11
10 12
3 6
3 16
8 11
20 1
...

output:

14

result:

ok single line: '14'

Test #3:

score: 5
Accepted
time: 0ms
memory: 1264kb

input:

20 30
4 13
7 5
2 8
2 19
12 4
10 16
4 15
15 5
11 10
1 15
11 6
20 2
11 13
10 13
5 9
20 6
15 8
4 1
19 1...

output:

16

result:

ok single line: '16'

Test #4:

score: 5
Accepted
time: 0ms
memory: 1268kb

input:

20 30
13 9
17 3
8 11
15 13
4 1
11 17
11 15
4 19
16 18
20 11
6 19
3 14
9 11
7 17
5 11
13 17
20 12
13 ...

output:

18

result:

ok single line: '18'

Test #5:

score: 5
Accepted
time: 0ms
memory: 1448kb

input:

2000 5000
708 453
572 852
1614 1917
1407 1159
1934 1233
688 172
1303 292
802 1571
1464 562
503 1659
...

output:

1949

result:

ok single line: '1949'

Test #6:

score: 5
Accepted
time: 3ms
memory: 1444kb

input:

2000 5000
1785 1100
260 653
50 1441
39 1157
1216 1677
1791 486
435 673
1830 257
972 1361
868 152
152...

output:

1937

result:

ok single line: '1937'

Test #7:

score: 5
Accepted
time: 3ms
memory: 1444kb

input:

2000 5000
1270 1265
1404 910
380 1260
615 661
1753 406
849 1506
1931 334
1907 926
1973 791
49 231
18...

output:

1942

result:

ok single line: '1942'

Test #8:

score: 5
Accepted
time: 0ms
memory: 1444kb

input:

2000 5000
482 1677
1320 654
797 413
883 93
870 388
379 505
1675 404
1552 29
1923 1293
1910 1682
214 ...

output:

1945

result:

ok single line: '1945'

Test #9:

score: 5
Accepted
time: 2ms
memory: 1452kb

input:

2000 5000
150 1583
474 1810
132 1383
1079 848
450 112
1868 1066
220 1816
246 538
993 845
1455 668
18...

output:

1943

result:

ok single line: '1943'

Test #10:

score: 5
Accepted
time: 3ms
memory: 1448kb

input:

2000 5000
617 199
32 1126
1554 1520
825 869
48 175
1433 295
898 1437
1894 1406
198 231
879 429
282 1...

output:

1961

result:

ok single line: '1961'

Test #11:

score: 5
Accepted
time: 136ms
memory: 8792kb

input:

100000 200000
467 88102
94619 59046
63290 96482
3400 43646
25426 95588
20105 2447
2643 33972
20699 2...

output:

92983

result:

ok single line: '92983'

Test #12:

score: 5
Accepted
time: 122ms
memory: 8792kb

input:

100000 200000
27398 80681
25414 65974
95017 4201
98299 1131
80294 27339
51487 27493
72073 81966
5334...

output:

92834

result:

ok single line: '92834'

Test #13:

score: 5
Accepted
time: 138ms
memory: 8804kb

input:

100000 200000
72059 3322
28860 17754
43114 10164
83599 61451
22795 86422
94403 75799
71197 17433
366...

output:

92889

result:

ok single line: '92889'

Test #14:

score: 5
Accepted
time: 133ms
memory: 8788kb

input:

100000 200000
81248 9937
29785 78778
16245 41542
73728 62922
58598 62765
93796 28166
27290 29783
784...

output:

92936

result:

ok single line: '92936'

Test #15:

score: 5
Accepted
time: 127ms
memory: 8784kb

input:

100000 200000
81053 73026
56619 38353
37925 53713
83161 4692
31847 87762
76858 5001
1292 82757
68814...

output:

93064

result:

ok single line: '93064'

Test #16:

score: 5
Accepted
time: 134ms
memory: 8792kb

input:

100000 200000
67275 33618
19697 91805
89698 29713
24087 66953
19687 980
1606 96935
39268 25232
3871 ...

output:

92954

result:

ok single line: '92954'

Test #17:

score: 5
Accepted
time: 127ms
memory: 8796kb

input:

100000 200000
21115 20555
52700 2269
51038 48309
70282 90215
22947 4210
84168 26599
72938 33830
1780...

output:

92901

result:

ok single line: '92901'

Test #18:

score: 5
Accepted
time: 134ms
memory: 8788kb

input:

100000 200000
62736 5878
46216 80273
33088 12121
43748 58403
91899 19150
44986 57634
97714 2625
3425...

output:

92871

result:

ok single line: '92871'

Test #19:

score: 5
Accepted
time: 138ms
memory: 8784kb

input:

100000 200000
4631 84264
55001 36495
79133 90543
16013 14038
83691 81215
86203 13841
64479 87645
201...

output:

92864

result:

ok single line: '92864'

Test #20:

score: 5
Accepted
time: 133ms
memory: 8804kb

input:

100000 200000
54746 86451
80666 46894
5710 18913
98631 55126
98380 87752
99701 94253
33741 48326
400...

output:

92905

result:

ok single line: '92905'