UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#201579#3221. 小L的旅行Josephcheng100202ms7796kbC++11907b2024-02-02 10:46:502024-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());
}

Details

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

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'