拓扑排序 UVA 10305

拓扑排序解决工程的先后问题

DFS在这方面较BFS有些先天优势，本身按工程的先后顺序搜索。答案由后向前存入stack

BFS加一个 in[] 数组，保证某一个工程（其前面有许多工程）在可行方案中尽量靠后放。答案由前向后存入vector

题目链接 https://vjudge.net/problem/UVA-10305

更多关于拓扑排序 https://blog.csdn.net/weixin_43918531/article/details/86740991

Description

John has n tasks to do. Unfortunately, the tasks are not independent and the execution of one task is only possible if other tasks have already been executed.

Input

The input will consist of several instances of the problem. Each instance begins with a line containing two integers, 1 ≤ n ≤ 100 and m. n is the number of tasks (numbered from 1 to n) and m is the number of direct precedence relations between tasks. After this, there will be m lines with two integers i and j, representing the fact that task i must be executed before task j. An instance with n = m = 0 will finish the input.

Output

For each instance, print a line with n integers representing the tasks in a possible order of execution

Sample Input

5 4
1 2
2 3
1 3
1 5
0 0

Sample Output

1 4 2 5 3

BFS与DFS（由于搜索方式不同）给出的可行方案也许、多半会不一样，像这题，BFS给出的方案同Sample Output ： 1 4 2 5 3，而DFS是：4 1 5 2 3

Code（DFS）

#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

bool vis[105];
stack<int> ans;
vector<int> v[105];

void dfs(int x)
{
    vis[x] = 1;
    for(int i = 0; i < v[x].size(); ++i)
        if( !vis[ v[x][i] ] )
            dfs(v[x][i]);
    ans.push(x);
}

int main()
{
    int n, m;
    while(cin >> n >> m && (n || m))
    {
        memset(vis, 0, sizeof(vis));///多组输入要加上
        for(int i = 0; i < 105; ++i)
            v[i].clear();
        for(int i = 0; i < m; ++i)
        {
            int a, b;
            cin >> a >> b;
            v[a].push_back(b);
        }
        for(int i = 1; i <= n; ++i)///不相连的多个图
            if(!vis[i])
                dfs(i);
        while(ans.size())
        {
            printf("%d%c", ans.top(), ans.size() == 1 ? '\n' : ' ');
            ans.pop();
        }
    }
    return 0;
}

Code(BFS)

#include <queue>
#include <cstdio>
#include <vector>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

int in[105];
vector<int> ans;
vector<int> v[105];

void bfs(queue<int> q)
{
    while(q.size())
    {
        int tem = q.front();
        ans.push_back(tem);
        q.pop();

        for(int i = 0; i < v[tem].size(); ++i)
        {
            in[ v[tem][i] ]--;
            if(!in[ v[tem][i] ])
                q.push(v[tem][i]);
        }
    }
}

int main()
{
    int n, m;
    while(cin >> n >> m && (n || m))
    {
        queue<int> q;
        memset(in, 0, sizeof(in));
        ans.clear();
        for(int i = 0; i < 105; ++i)
            v[i].clear();

        int a, b;
        for(int i = 0; i < m; ++i)
        {
            cin >> a >> b;
            v[a].push_back(b);
            in[b]++;
        }

        for(int i = 1; i <= n; ++i)
            if(!in[i])
                q.push(i);
        bfs(q);

        for(int i = 0; i < ans.size(); ++i)
            printf("%d%c", ans[i], i == ans.size() - 1 ? '\n' : ' ');
    }
    return 0;
}