python/TangDou/AcWing/CheckCircle/AcWing 848_dfs_1.cpp

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10, M = N << 1;
// AcWing 848. 有向图的拓扑序列

//邻接表
int e[M], h[N], idx, ne[M];
void add(int a, int b) {
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}

/*
0代表未访问
1代表是这一阶段正在访问的（这一阶段指的是两个元素在同一个递归中）
2代表访问完毕
*/
int color[N];

vector<int> res; //拓扑序结果数组

bool dfs(int u) {
    color[u] = 1;
    for (int i = h[u]; ~i; i = ne[i]) {
        int j = e[i];
        if (color[j] == 1) return true;
        if (color[j] == 0 && dfs(j)) return true;
    }
    color[u] = 2;
    //利用递归的规则，在把自己为出发点的一组节点跑完，才把自己加入路径，它的孩子在它之前已经加入了路径
    res.push_back(u);
    return false;
}

int main() {
    memset(h, -1, sizeof h);
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        add(a, b);
    }

    bool flag = false;
    for (int i = 1; i <= n; i++)
        if (!color[i]) {
            flag = dfs(i); //枚举每个点，如果没有访问过，就作为起点搜索
            if (flag) break;
        }

    if (flag)
        puts("-1");
    else {
        reverse(res.begin(), res.end());

        for (int i = 0; i < res.size(); i++)
            printf("%d%c", res[i], i == res.size() - 1 ? '\n' : ' ');
    }
    return 0;
}
/*
无环测试用例:
3 3
1 2
2 3
1 3
答案:
1 2 3


有环测试用例：
3 3
1 2
2 3
3 1
答案:应该输出有环，-1
实际： 1 2 3
这是有问题的~,需要新方法判环~
*/