-
Notifications
You must be signed in to change notification settings - Fork 2
/
Copy path100000623-02.cpp
155 lines (141 loc) · 3.7 KB
/
100000623-02.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
/*
* hint:
* 本题使用两种方法，邻接矩阵和邻接表两种
* 邻接矩阵一直无法 AC，原因尚未找出
*
* 给出两组测试样例
* 第一组：测试输入超范围数据
3 2
9 5
1 3
0 0
* 第二组：测试输入重复数据
3 2
0 2
0 2
0 0
*
* 使用邻接表方法时，上述两种输入无需额外处理，因为
* 当超出范围时，邻接表方法计算出的 num 一定不等于 n，因此顺利返回 NO
* 当重复输入时，邻接表方法的重复计算恰使结果正确
*
* 使用邻接矩阵时，代码中两行 VITAL 注释标注的行提供了非法数据解决方案
*
* 其他一定尚有未测试出的不一致内容。但是方法二通过了测试并不能说明邻接表法一定是正确的
*/
// // method 1: adjacency matrix
// #include <cstdio>
// #include <queue>
// #include <cstring>
// #include <set>
// #define MAXN 110
// using namespace std;
// int n, m;
// bool graph[MAXN][MAXN];
// int in_degree[MAXN];
// set<pair<int, int>> inputs;
// bool topological_sort()
// {
// // step 0: initialize
// int num = 0;
// queue<int> q;
// // step 1: push vertexes whose in-degrees are 0
// for (int i = 0; i < n; i++)
// if (in_degree[i] == 0)
// q.push(i);
// // step 2: bfs
// while (q.size())
// {
// int u = q.front();
// q.pop();
// num++;
// for (int v = 0; v < n; v++)
// if (graph[u][v] == true)
// {
// in_degree[v]--;
// if (in_degree[v] == 0)
// q.push(v);
// }
// }
// if (num == n) return true;
// else return false;
// }
// int main()
// {
// while (scanf("%d %d", &n, &m) != EOF && n != 0 && m != 0)
// {
// memset(in_degree, 0, sizeof(in_degree));
// // memset(graph, false, sizeof(graph));
// fill(graph[0], graph[0] + MAXN * MAXN, false);
// bool is_valid = true;
// for (int i = 0; i < m; i++)
// {
// int x, y;
// scanf("%d %d", &x, &y);
// if (is_valid && !(0 <= x && x < n && 0 <= y && y < n)) // VITAL. deal with invalid inputs
// is_valid = false;
// if (inputs.count({x, y}) == 0) // VITAL. deal with duplicated inputs
// {
// inputs.insert({x, y});
// graph[x][y] = true;
// in_degree[y]++;
// }
// }
// printf(is_valid && topological_sort() ? "YES\n" : "NO\n");
// }
// return 0;
// }
// method 2: adjacency list
#include <cstdio>
#include <vector>
#include <queue>
#include <cstring>
#define MAXN 110
using namespace std;
int n, m;
vector<int> adj[MAXN];
int in_degree[MAXN];
bool topological_sort()
{
// step 0: initialize
int num = 0;
queue<int> q;
// step 1: push vertexes whose in-degrees are 0
for (int i = 0; i < n; i++)
if (in_degree[i] == 0)
q.push(i);
// step 2: bfs
while (q.size())
{
int u = q.front();
q.pop();
num++;
for (int i = 0; i < adj[u].size(); i++)
{
int v = adj[u][i];
in_degree[v]--;
if (in_degree[v] == 0)
q.push(v);
}
}
if (num == n) return true;
else return false;
}
int main()
{
while (scanf("%d %d", &n, &m) != EOF && n != 0 && m != 0)
{
memset(in_degree, 0, sizeof(in_degree));
for (int i = 0; i < MAXN; i++)
adj[i].clear();
for (int i = 0; i < m; i++)
{
int x, y;
scanf("%d %d", &x, &y);
adj[x].push_back(y);
in_degree[y]++;
}
printf(topological_sort() ? "YES\n" : "NO\n");
}
return 0;
}