AcWing - 有向图的拓扑序列(拓扑排序)

题目链接:https://www.acwing.com/problem/content/850/
时/空限制：1s / 64MB

题目描述

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

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

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

输入格式

第一行包含两个整数n和m

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

输出格式

共一行，如果存在拓扑序列，则输出拓扑序列。

否则输出-1。

数据范围

1≤n,m≤10^5

输入样例

3 3
1 2
2 3
1 3

输出样例

1 2 3

解题思路

题意:给你一个有向图，求出这个图的拓扑序列。
思路:直接拓扑排序就行了。

Accepted Code:

/* 
 * @Author: lzyws739307453 
 * @Language: C++ 
 */
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5 + 5;
const int MAXM = MAXN << 1;
const int inf = 0x3f3f3f3f;
struct AdjTab {
    int u, v;
    AdjTab() {}
    AdjTab(int u, int v) : u(u), v(v) {}
}e[MAXN];
int degree[MAXN], spt[MAXN], f[MAXN], Adj = 0;
void Add_Adj(int u, int v) {
    e[++Adj] = AdjTab(f[u], v);
    f[u] = Adj;
}
int TopSort(int n) {
    int top = 0;
    queue <int> Q;
    for (int i = 1; i <= n; i++)
        if (!degree[i])
            Q.push(i);
    while (!Q.empty()) {
        int u = Q.front();
        Q.pop();
        spt[top++] = u;
        for (int i = f[u]; ~i; i = e[i].u) {
            int v = e[i].v;
            degree[v]--;
            if (!degree[v])
                Q.push(v);
        }
    }
    return top;
}
int main() {
    int n, m;    
    scanf("%d%d", &n, &m);
    memset(f, -1, sizeof(f));
    for (int i = 0; i < m; i++) {
        int u, v;
        scanf("%d%d", &u, &v);
        Add_Adj(u, v);
        degree[v]++;
    }
    int cnt = TopSort(n);
    if (cnt < n)
        printf("-1\n");
    else {
        for (int i = 0; i < cnt; i++)
            printf("%d ", spt[i]);
        printf("\n");
    }
    return 0;
}