判断给定图是否存在合法拓扑序列（拓扑排序及其优化）

数据结构实验之图论十：判断给定图是否存在合法拓扑序列
Description
给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。

Input
输入包含多组，每组格式如下。

第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)

后面m行每行两个整数a b，表示从a到b有一条有向边。

Output
若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。

Sample
Input
1 0
2 2
1 2
2 1
Output
YES
NO

每次找一个入度为0的节点，删除该节点，如果找不到，则说明不存在合法拓扑序列，有环存在。
我们可以通过队列来存在入度为零的节点，以此来优化


普通暴力找入度为0的节点代码：

#include
using namespace std;
int s[12];
int ma[12][12];
int vis[12];
int u, v, n, m, i, j, k;
int main()
{
ios::sync_with_stdio(false);
while (cin >> n >> m)
{
memset(s, 0, sizeof(s));
memset(ma, 0, sizeof(ma));
memset(vis, 0, sizeof(vis));
for (int i = 0; i < m; i++)
{
cin >> u >> v;
ma[u][v] = 1;
s[v]++;
}
for (k = 0; k < n; k++)
{
int flag = 1;
for (i = 1; i <= n; i++)
{
if (s[i] == 0 && vis[i] == 0)
{
vis[i] = 1;
flag = 0;
for (j = 1; j <= n; j++)
{
if (ma[i][j]) {
s[j]--;
}
}
break;
}
}
if (flag) break;
}
if (k < n)
cout << "NO\n";
else
cout << "YES\n";
}
}


利用队列代码：

#include
using namespace std;
int s[12];
int ma[12][12];
int u, v, n, m, i, k;
int main() {
ios::sync_with_stdio(false);
while (cin >> n >> m) {
memset(s, 0, sizeof(s));
memset(ma, 0, sizeof(ma));
queue<int> q;
k = 0;
for (int i = 0; i < m; i++) {
cin >> u >> v;
ma[u][v] = 1;
s[v]++;
}
for (int i = 1; i <= n; i++) {
if (!s[i]) q.push(i);
}
while (!q.empty()) {
int t = q.front();
q.pop();
k++;
for (i = 1; i <= n; i++) {
if (ma[u][i]) {
s[i]--;
if (!s[i]) q.push(i);
}
}
}
if (k == n)
cout << "YES\n";
else
cout << "NO\n";
}
}


链式前向星存图代码

#include
using namespace std;
int s[12];
int h[12];
int cnt;
struct node {
int v, next;
} a[12];
void add(int u, int v) {
a[++cnt].v = v;
a[cnt].next = h[u];
h[u] = cnt;
}
int u, v, n, m, i, k;
int main() {
ios::sync_with_stdio(false);
while (cin >> n >> m) {
cnt = 0;
memset(h, 0, sizeof(h));
memset(s, 0, sizeof(s));
queue<int> q;
k = 0;
for (int i = 0; i < m; i++) {
cin >> u >> v;
add(u, v);
s[v]++;
}
for (int i = 1; i <= n; i++) {
if (!s[i]) q.push(i);
}
while (!q.empty()) {
int t = q.front();
q.pop();
k++;
for (i = h[t]; i; i = a[i].next) {
s[a[i].v]--;
if (!s[a[i].v]) q.push(i);
}
}
if (k == n)
cout << "YES\n";
else
cout << "NO\n";
}
}