#2398. 图函数
图函数
图函数
题目描述
全国青少年信息学奥林匹克竞赛 Day1(A 卷)图函数(graph) 图函数(graph) 【题目描述】 对于一张n 个点m 条边的有向图G(顶点从1 ∼n 编号),定义函数f(u, G):
- 初始化返回值cnt = 0,图G′ = G。
- 从1 至n 按顺序枚举顶点v,如果当前的图G′ 中,从u 到v 与从v 到u 的路 径都存在,则将cnt + 1,并在图G′ 中删去顶点v 以及与它相关的边。
- 第2 步结束后,返回值cnt 即为函数值。 现在给定一张有向图G,请你求出h(G) = f(1, G) + f(2, G) + · · · + f(n, G) 的值。 更进一步地,记删除(按输入顺序给出的)第1 ∼i 条边后的图为Gi(1 ≤i ≤m), 请你求出所有h(Gi) 的值。 【输入格式】 从文件graph.in 中读入数据。 第一行两个整数n, m 表示图的点数与边数。 接下来m 行每行两个整数,第i 行的两个整数xi, yi 表示一条有向边xi →yi。 数据保证xi̸ = yi 且同一条边不会给出多次。 【输出格式】 输出到文件graph.out 中。 输出一行m + 1 个整数,其中第一个数表示给出的完整图G 的h(G) 值。第i (2 ≤i ≤m + 1)个整数表示h(Gi−1)。 【样例1 输入】 1 4 6 2 2 3 3 3 2 4 4 1 5 1 4 6 2 1 7 3 1 【样例1 输出】 1 6 5 5 4 4 4 4 第6 页 共7 页
全国青少年信息学奥林匹克竞赛 Day1(A 卷)图函数(graph) 【样例1 解释】 对于给出的完整图G:
- f(1, G) = 1,过程中删除了顶点1。
- f(2, G) = 1,过程中删除了顶点2。
- f(3, G) = 2,过程中删除了顶点2, 3。
- f(4, G) = 2,过程中删除了顶点1, 4。 【样例2】 见选手目录下的graph/graph2.in 与graph/graph2.ans。 【数据范围】 对于所有测试数据:2 ≤n ≤1000,1 ≤m ≤2 × 105,1 ≤xi, yi ≤n。 每个测试点的具体限制见下表: 测试点编号 n ≤ m ≤ 1 ∼4 10 10 5 ∼11 100 2000 12 ∼20 1000 5000 21 ∼25 2 × 105 第7 页 共7 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
4 6
2 3
3 2
4 1
1 4
2 1
3 1
6 5 5 4 4 4 4
样例 2
100 1000
75 93
1 88
18 23
9 93
75 10
1 57
70 92
3 25
92 56
14 8
82 19
59 73
15 68
58 13
27 57
47 8
3 79
84 100
84 52
5 26
39 86
48 13
78 68
58 61
49 44
1 67
97 64
81 57
71 39
42 50
54 85
51 9
6 48
65 42
100 60
1 54
56 64
47 48
64 46
49 98
25 80
62 3
41 70
81 23
73 74
79 95
26 92
22 27
39 34
67 1
9 76
100 30
32 83
18 73
14 74
67 59
38 96
91 78
71 60
99 55
52 36
25 62
79 68
14 44
9 30
37 84
19 69
32 72
9 88
47 25
30 24
49 58
95 85
33 63
62 86
65 5
16 64
93 51
8 25
82 74
95 25
17 27
28 59
13 98
92 40
82 64
76 30
57 97
1 2
13 55
72 43
56 20
52 57
18 64
100 78
83 66
64 38
50 96
28 23
56 90
78 18
5 30
54 52
91 1
27 48
87 16
93 11
3 41
28 13
31 64
53 6
15 45
45 55
95 59
31 99
27 29
16 26
5 56
92 84
84 61
5 81
93 15
83 9
3 40
69 76
88 70
12 35
76 74
19 74
81 48
70 45
2 30
55 57
31 65
48 1
96 66
16 73
58 67
83 96
77 19
79 93
24 11
93 82
47 53
3 7
28 92
2 6
87 5
92 35
11 23
37 61
46 69
36 25
3 44
72 63
57 85
21 49
87 8
2 77
80 47
79 88
96 29
25 90
3 71
4 46
49 97
51 85
47 37
59 37
61 65
10 22
2 91
8 20
51 52
18 97
80 95
68 47
93 27
51 7
74 78
38 67
72 25
93 99
71 95
44 100
82 43
19 17
53 29
23 48
77 35
83 40
39 62
2 40
14 35
7 86
30 22
25 93
88 76
88 16
15 49
18 37
25 81
50 45
4 37
20 67
22 6
28 75
4 16
2 81
62 72
54 44
62 33
44 10
43 5
68 16
48 57
65 97
75 7
95 21
54 74
35 2
26 9
3 98
3 85
43 73
62 45
2 3
61 63
42 3
36 46
58 50
67 49
12 64
63 86
71 57
87 28
57 78
76 64
1 29
97 99
99 68
67 66
44 36
31 8
38 26
6 79
35 10
20 60
57 54
70 87
10 43
93 80
45 2
40 55
9 95
10 29
49 9
22 47
91 80
25 24
1 75
81 56
57 51
28 100
6 78
80 18
55 25
69 78
68 50
29 33
34 27
59 26
78 76
16 43
57 90
56 31
48 88
70 34
63 19
74 27
65 39
1 26
69 19
60 52
19 20
63 72
26 37
99 49
93 62
95 66
3 84
47 16
95 65
28 33
85 61
44 49
89 90
12 6
52 27
48 95
20 38
81 3
63 59
99 89
21 90
20 21
64 100
21 22
91 18
56 99
40 71
16 90
92 7
21 74
44 27
44 60
11 92
54 89
73 75
2 7
30 29
84 74
4 66
29 9
33 18
73 93
83 26
36 68
95 62
83 94
26 44
4 36
86 13
98 59
8 82
90 99
85 8
19 49
48 51
46 27
94 19
25 56
82 42
93 24
72 65
47 96
7 73
85 14
83 92
99 92
65 71
62 35
68 12
18 87
40 33
17 82
45 74
51 2
59 10
75 83
39 9
9 44
18 12
92 67
65 28
91 75
67 53
9 13
90 29
29 12
76 87
96 41
59 30
83 13
59 4
73 10
83 69
1 55
58 76
9 3
52 85
71 47
70 52
49 11
88 39
30 15
69 96
99 69
37 97
83 56
34 79
40 37
37 12
33 35
5 98
18 40
87 20
9 42
22 69
44 67
23 85
94 22
29 41
17 65
3 4
90 3
30 87
30 21
32 57
98 68
32 68
76 38
97 69
52 94
86 57
43 47
7 18
80 52
63 65
42 100
59 13
6 9
78 89
55 37
60 20
51 13
56 59
3 38
41 53
60 54
11 56
22 98
18 96
85 28
50 30
4 40
18 95
86 32
19 52
17 91
90 7
84 62
85 76
94 58
15 44
86 58
47 62
12 5
23 29
31 22
49 50
79 73
30 25
78 2
16 12
65 44
85 1
35 26
19 39
71 24
13 90
86 55
72 76
94 95
13 33
49 70
80 75
1 46
92 55
99 19
85 73
13 66
21 20
62 16
35 99
39 73
87 27
24 94
53 20
11 52
59 1
15 18
17 5
100 59
50 37
1 70
8 72
49 24
37 20
16 68
76 92
74 9
26 66
41 15
78 75
49 79
28 73
48 45
99 31
53 22
81 42
98 63
88 10
79 100
10 14
9 66
59 97
11 50
67 58
46 39
6 22
22 46
8 92
86 99
66 61
72 78
67 46
75 4
53 42
89 8
78 51
54 20
56 29
71 33
65 51
81 62
55 8
70 100
63 16
72 30
57 95
61 17
99 85
82 13
18 6
5 89
97 41
93 69
50 1
77 2
82 35
27 30
9 96
74 46
57 64
83 80
33 20
64 39
72 22
28 51
74 43
19 60
51 26
83 58
76 84
65 73
52 69
75 82
75 20
53 32
2 35
86 34
61 58
93 25
41 95
47 10
39 24
26 19
16 58
88 100
98 5
98 21
35 39
9 28
41 8
33 6
22 95
3 39
5 9
63 43
71 42
7 2
21 77
95 38
87 33
17 60
65 57
59 62
34 77
79 5
14 77
64 52
48 63
88 61
43 45
31 52
64 37
8 46
40 36
53 25
48 11
2 10
25 63
91 92
5 74
79 32
36 83
6 37
65 52
17 71
90 93
26 32
35 12
79 27
33 61
20 18
3 76
14 50
69 32
68 9
16 1
34 78
55 30
31 59
52 65
23 74
58 32
54 83
62 82
95 7
20 78
85 19
61 12
69 99
21 30
56 27
61 39
69 62
31 37
82 93
18 46
84 25
78 1
96 98
46 93
75 19
100 96
90 85
61 25
23 52
12 52
11 95
30 58
77 67
35 32
88 90
70 60
90 52
79 71
11 40
79 54
33 62
1 3
94 69
75 62
45 66
47 13
52 53
55 70
73 6
15 25
84 11
99 10
59 78
9 90
93 45
49 87
55 49
84 3
65 49
89 10
74 11
40 75
61 96
33 64
31 24
5 21
18 43
2 50
41 39
33 73
41 49
21 24
60 77
21 51
33 10
28 79
60 28
72 35
55 15
66 36
78 70
31 11
78 50
2 39
19 2
8 41
97 29
46 13
92 68
52 2
45 97
8 53
64 40
98 19
20 62
76 11
67 15
21 4
78 97
74 93
10 34
89 43
9 15
60 36
50 58
33 57
19 91
72 59
67 86
82 99
29 71
87 19
9 36
33 83
69 30
24 52
10 70
14 71
100 5
39 65
85 70
74 60
93 9
79 20
88 35
27 14
11 31
31 47
96 50
79 64
34 23
36 44
17 100
68 97
21 37
9 6
46 70
90 20
99 18
3 2
20 49
94 74
20 70
58 89
2 82
18 21
89 32
42 5
78 12
3 82
90 95
85 36
1 33
44 24
58 37
66 68
1 95
100 92
10 25
29 69
76 93
32 8
52 35
16 22
74 14
13 74
54 98
74 28
7 58
83 98
58 36
32 51
59 84
96 56
20 80
21 69
7 54
18 13
26 20
52 60
1 94
10 5
81 51
74 84
71 98
36 28
12 89
57 6
59 14
46 43
32 78
55 80
46 44
46 14
42 61
41 2
21 71
3 20
11 76
26 57
96 86
24 88
18 8
49 1
3 49
83 77
89 66
57 67
80 43
76 4
83 48
66 38
73 95
24 43
94 75
4 14
97 91
8 97
90 8
15 91
27 37
5 10
12 13
7 24
40 41
14 26
28 71
64 56
45 13
36 35
87 17
41 40
2 71
37 66
18 34
67 95
8 52
52 86
24 92
87 81
65 76
31 45
26 30
55 66
28 80
86 19
99 3
7 51
2 56
32 90
24 55
79 76
29 48
84 67
28 50
64 17
37 6
94 59
40 85
99 84
80 84
63 60
76 94
11 64
46 2
94 87
20 47
27 88
30 70
35 47
16 61
58 65
16 86
43 27
22 9
48 87
11 45
89 12
34 95
70 6
77 70
1 91
46 25
69 73
49 13
64 35
89 86
21 94
43 39
31 93
94 39
23 43
24 19
69 39
99 71
27 67
29 90
13 25
80 46
14 11
40 84
91 93
93 48
72 8
100 15
61 10
32 2
85 34
42 80
81 90
49 43
20 86
57 46
13 46
81 70
24 71
34 96
79 35
48 54
20 54
6 32
85 60
89 27
2 49
61 92
17 49
6 10
39 36
95 76
64 87
23 63
14 96
41 93
51 56
55 98
56 87
14 97
36 100
50 31
26 83
12 4
48 66
98 42
18 90
1 37
32 86
16 60
54 24
75 88
65 85
44 73
20 14
55 85
4 61
66 47
80 32
44 76
54 67
35 9
7 57
89 54
37 77
91 76
45 92
47 87
63 44
88 1
51 28
72 47
69 52
38 87
50 69
66 39
79 22
21 88
31 9
63 25
98 4
31 14
4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4689 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4647 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4645 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4642 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4637 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4631 4630 4630 4630 4630 4618 4618 4618 4615 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4592 4552 4552 4552 4552 4552 4552 4552 4552 4552 4552 4552 4552 4552 4552 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4527 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4520 4462 4462 4462 4462 4462 4462 4462 4430 4430 4430 4430 4427 4427 4427 4427 4427 4427 4427 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4378 4375 4375 4375 4375 4375 4375 4375 4375 4375 4375 4375 4375 4375 4375 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4374 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4338 4334 4334 4334 4334 4334 4334 4334 4334 4334 4296 4296 4296 4296 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4294 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4287 4216 4216 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4186 4178 4178 4178 4178 4178 4178 4178 4178 4178 4157 4157 4157 4157 4157 4157 4115 4115 4115 4115 4115 4115 4115 4115 4115 4115 4115 4115 4074 4074 4074 4074 4074 4064 4064 4064 4064 4064 4064 4064 4064 4064 4055 3957 3957 3957 3957 3957 3957 3957 3957 3903 3884 3884 3884 3884 3884 3884 3884 3798 3787 3787 3787 3787 3787 3787 3787 3705 3705 3705 3705 3705 3704 3704 3698 3698 3684 3570 3570 3570 3570 3570 3570 3570 3531 3531 3453 3453 3453 3453 3453 3368 3368 3368 3368 3368 3368 3368 3368 3267 3267 3190 3190 3190 3190 3190 3190 3128 3057 3015 3015 3015 3015 3015 2993 2993 2993 2903 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2890 2888 2888 2888 2863 2765 2673 2673 2673 2673 2530 2530 2530 2530 2530 2530 2530 2530 2530 2530 2530 2530 2530 2530 2526 2526 2526 2526 2526 2526 2441 2441 2406 2292 2292 2292 2292 2292 2292 2292 2279 2279 2279 2279 2279 2279 2279 2279 2279 2279 2195 2195 2166 2165 2165 2077 2068 2068 2068 2068 2001 2001 2001 1999 1999 1999 1999 1999 1995 1995 1995 1995 1995 1935 1935 1935 1935 1935 1935 1935 1935 1935 1935 1935 1863 1863 1803 1803 1793 1793 1775 1775 1775 1775 1775 1775 1763 1763 1688 1688 1688 1664 1625 1625 1546 1546 1546 1534 1534 1534 1467 1466 1466 1466 1382 1382 1382 1238 1238 1238 1238 1238 1204 1204 1204 1204 1204 1204 1134 1105 1105 1060 1060 1056 1056 1011 1011 1011 1011 989 989 989 989 989 989 989 915 915 790 790 790 790 790 790 790 790 790 790 768 768 755 755 755 748 748 748 748 748 748 740 730 719 719 719 719 719 711 711 711 710 667 667 650 528 527 527 519 519 519 519 500 365 365 365 365 365 365 362 362 362 362 362 362 362 362 362 362 362 359 352 352 352 351 294 219 219 219 175 170 170 170 170 169 169 169 169 169 158 148 148 148 148 148 140 140 140 140 124 124 124 124 124 124 124 124 124 124 124 115 115 115 115 115 115 115 115 115 115 115 115 115 115 110 110 110 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100