题目描述

给定一个n个点m条边的有向图，点的编号是1到n，图中可能存在重边和自环。

请输出任意一个该有向图的拓扑序列，如果拓扑序列不存在，则输出-1。

若一个由图中所有点构成的序列A满足：对于图中的每条边(x, y)，x在A中都出现在y之前，则称A是该图的一个拓扑序列。

输入格式
第一行包含两个整数n和m

接下来m行，每行包含两个整数x和y，表示存在一条从点x到点y的有向边(x, y)。

输出格式
共一行，如果存在拓扑序列，则输出任意一个合法的拓扑序列即可。

否则输出-1。

数据范围
1≤n,m≤105
输入样例：
3 3
1 2
2 3
1 3
输出样例：
1 2 3

蒟蒻一只，理解不了y总的邻接表所以用stl来偷懒。
第一次写题解，可能有疏误，求大佬轻喷QWQ。

C++ 代码

#pragma GCC optmize(2)
#include <bits/stdc++.h>
#define int long long
#define endl '\n'

using namespace std;
const int N = 1e5 + 10;
int n, m;
vector<int>g[N];
int d[N];//入
queue<int>q;
vector<int>ans;
void solve() {
    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        g[a].push_back(b);
        d[b]++;
    }
    for (int i = 1; i <= n; i++) {
        if (!d[i]) {
            q.push(i);
        }
    }

    while (q.size()) {
        int u = q.front();
        ans.push_back(u);
        q.pop();
        for (auto i : g[u]) {
            if (--d[i] == 0) {
                q.push(i);
            }
        }

    }
    if (ans.size() < n) {
        cout << "-1" << endl;
        return;
    }
    for (auto i : ans) {
        cout << i << " ";
    }
    cout << endl;

}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    solve();
}