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

数据结构实验之图论十：判断给定图是否存在合法拓扑序列
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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 <bits/stdc++.h>
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";
    }
}