ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#214854 | #2683. Tourist Reform | linzhiyi | 100 | 1334ms | 8804kb | C++ | 1014b | 2024-11-22 19:38:51 | 2024-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;
}
Details
小提示:点击横条可展开更详细的信息
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'