ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#201579 | #3221. 小L的旅行 | Josephcheng | 100 | 202ms | 7796kb | C++11 | 907b | 2024-02-02 10:46:50 | 2024-02-02 14:47:26 |
answer
#include<bits/stdc++.h>
using namespace std;
int n,m,u,v,pos;
int head[100005],d[100005],d2[100005];
queue<pair<int,int>> q;
struct Edge
{
int u,v,nxt;
}e[600005];
void addEdge(int u,int v)
{
e[++pos]={u,v,head[u]};
head[u]=pos;
d[v]++;
}
int toposort(){
int res=0;
queue<pair<int,int>> q;
for(int i=1;i<=n;i++)
if(d[i]==0) q.push({i,1});
while(q.size()){
int u=q.front().first,len=q.front().second;
q.pop();
res=max(res,len);
for(int i=head[u];i;i=e[i].nxt){
int v=e[i].v;
d[v]--;
if(d[v]==0) q.push({v,len+1});
}
}
return res;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=m;i++){
scanf("%d%d",&u,&v);
q.push({u,v});
d2[u]++,d2[v]++;
}
while(q.size()){
int u=q.front().first,v=q.front().second;
q.pop();
if(d2[u]>d2[v]) addEdge(v,u);
if(d2[u]<d2[v]) addEdge(u,v);
}
printf("%d",toposort());
}
详细
小提示:点击横条可展开更详细的信息
Test #1:
score: 10
Accepted
time: 0ms
memory: 1248kb
input:
10 25 10 2 6 1 3 4 6 5 9 8 4 9 1 7 7 8 2 9 4 7 5 2 7 6 2 1 2 7 6 10 1 4 6 9 10 9 3 6 9 3 3 1 2 3 6 4...
output:
4
result:
ok single line: '4'
Test #2:
score: 10
Accepted
time: 0ms
memory: 1248kb
input:
15 75 4 9 2 15 13 10 4 8 8 13 14 8 4 7 14 2 3 6 13 3 7 15 8 11 3 4 3 14 4 1 3 10 7 9 4 14 6 13 1 7 6...
output:
5
result:
ok single line: '5'
Test #3:
score: 10
Accepted
time: 0ms
memory: 1244kb
input:
20 130 4 12 15 14 20 11 19 16 9 17 15 1 10 9 13 1 17 13 9 3 2 3 20 7 2 17 14 1 8 19 1 5 19 12 19 13 ...
output:
7
result:
ok single line: '7'
Test #4:
score: 10
Accepted
time: 0ms
memory: 1244kb
input:
30 200 9 6 28 24 16 20 19 16 21 12 24 18 7 22 25 16 28 3 25 17 2 9 30 19 3 4 22 6 21 19 3 2 22 1 15 ...
output:
8
result:
ok single line: '8'
Test #5:
score: 10
Accepted
time: 0ms
memory: 1264kb
input:
50 600 25 33 49 29 14 46 2 32 35 49 6 34 32 39 18 4 11 41 44 28 1 8 48 27 36 20 27 25 48 32 14 9 25 ...
output:
14
result:
ok single line: '14'
Test #6:
score: 10
Accepted
time: 0ms
memory: 1300kb
input:
100 2000 44 70 95 38 13 50 24 49 47 25 13 37 8 5 9 2 56 96 9 77 88 39 59 53 10 54 12 26 23 2 8 98 10...
output:
21
result:
ok single line: '21'
Test #7:
score: 10
Accepted
time: 14ms
memory: 3428kb
input:
1000 120000 80 154 971 15 764 609 346 200 729 626 240 531 331 181 649 121 785 303 281 923 167 848 15...
output:
69
result:
ok single line: '69'
Test #8:
score: 10
Accepted
time: 59ms
memory: 7432kb
input:
57843 300000 47356 32927 28944 46337 25009 34267 48808 22798 8549 6875 10636 3869 38574 38701 45054 ...
output:
16
result:
ok single line: '16'
Test #9:
score: 10
Accepted
time: 63ms
memory: 7256kb
input:
34687 300000 5802 27361 20831 20754 9878 5780 6163 33670 29413 13662 20791 586 9888 2047 21871 26011...
output:
21
result:
ok single line: '21'
Test #10:
score: 10
Accepted
time: 66ms
memory: 7796kb
input:
100000 300000 27608 49951 64703 75998 39918 13590 23350 12989 3425 97988 68164 55657 27379 45038 718...
output:
12
result:
ok single line: '12'