描述

给定一个包含nn个点mm条边的有向无环图，求出该图的拓扑序。若图的拓扑序不唯一，输出任意合法的拓扑序即可。若该图不能拓扑排序，输出-1−1。

输入描述：

第一行输入两个整数n,mn,m ( 1\le n,m \le 2\cdot 10^51≤n,m≤2⋅105)，表示点的个数和边的条数。
接下来的mm行，每行输入两个整数u_i,v_iui,vi (1\le u,v \le n1≤u,v≤n)，表示u_iui到v_ivi之间有一条有向边。

输出描述：

若图存在拓扑序，输出一行nn个整数，表示拓扑序。否则输出-1−1。

示例1

输入： 
5 4
1 2
2 3
3 4
4 5
复制
输出： 
1 2 3 4 5

解题思路：
该题目和检测循环依赖类似，但检测循环依赖的数量级小，使用图的遍历可以解决，本题数量级大，使用图的遍历会超时。
看题解使用每个节点“入度”统计来解决 
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
//使用检测循环依赖相同的解法会超时
/*vector<int>path;
vector<int>res;
vector<int>visit;
bool flag = false;
void bfs(vector<vector<int>>&dp, int t) {
    if (find(path.begin(), path.end(), t) != path.end()) {
        flag = true; //有环
        return;
    }
    if (visit[t]) {
        return;
    }
    visit[t] = 1;
    path.push_back(t);
    for (int i = 0; i < dp[t].size(); i++) {
        if (flag) break;
        bfs(dp, dp[t][i]);
    }
    path.pop_back();
    res.push_back(t);
}

int main() {
    int n, m;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        vector<vector<int>>dp(n+1, vector<int>());
        path.resize(n);
        res.resize(n);
        visit.resize(n, 0);
        for (int i = 0; i < m; i++)
        {
            int tmp1, tmp2;
            cin >> tmp1;
            cin >> tmp2;
            dp[tmp1].push_back(tmp2);
        }
        for (int i = 0; i < n; i++) {
            if (flag) break;
            bfs(dp, i+1);
        }
        if (flag) {
            cout << -1 << endl;
            break;
        }
        reverse(res.begin(), res.end());
        cout << res[0];
        for (int i = 1; i < res.size(); i++) {
            if (res[i] != 0) {
                cout << " " << res[i];
            }
        }
        cout << endl;
    }
    return 0;
}*/
int main() {
    int n, m;
    while (cin >> n >> m) { // 注意 while 处理多个 case
        vector<vector<int>>dp(n+1, vector<int>());
        vector<int>inDegree(n+1);
        queue<int> que;
        vector<int>res;
        int cnt = 0;
        for (int i = 0; i < m; i++)
        {
            int tmp1, tmp2;
            cin >> tmp1;
            cin >> tmp2;
            dp[tmp1].push_back(tmp2);
            inDegree[tmp2]++;
        }
        
        for (int i = 1; i <= n; i++) {
            if (inDegree[i] == 0) {
                que.push(i);
            }
        }
        while (!que.empty()) {
            int u = que.front();
            res.push_back(u);
            que.pop();
            for (int i = 0; i < dp[u].size(); i++) {
                inDegree[dp[u][i]]--;
                if (inDegree[dp[u][i]] == 0) {
                    que.push(dp[u][i]);
                }
            }
            cnt++;
        }
        if (cnt != n) {
            cout << -1 << endl;
            continue;
        }
        cout << res[0];
        for (int i = 1; i < res.size(); i++) {
            cout << " " << res[i];
        }
        cout << endl;

    }
    return 0;
}
// 64 位输出请用 printf("%lld")