【BFS】有向图的拓扑序列

题目

848. 有向图的拓扑序列

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

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

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

输入格式

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

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

输出格式

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

否则输出 $-1$ 。

数据范围

$1 \le n,m \le 10^5$

输入样例：

输出样例：

1 2 3

解题

方法一：BFS

思路

基本概念：

有向无环图才存在拓扑排序。
在拓扑序中，图中每个顶点只会出现一次，若存在一条从顶点 A 到顶点 B 的路径，那么在序列中顶点 A 出现在顶点 B 的前面。
有向图中，对于一个顶点，进入该点的路径的条数叫做入度，从该点出去的路径的条数叫做出度。

实现拓扑排序：

首先比起一般的图，多维护一个所有顶点的入度(ind)，在加入边时更新入度。
维护一个队列(que)，把所有入度为 $0$ 的点放入队列。
在队列不为空的条件下循环：
- 从队头取出一个顶点(curr)。
- 遍历这个顶点(j)的出边，删除 curr -> j 这条边（其实就是把顶点 j 的入度减一），如果删完之后 j 的入度为 $0$ ，就把 j 入队。
循环结束后，如果所有点都入队过说明存在拓扑序列，否则不存在拓扑序列。
如果存在拓扑排序，拓扑排序就是顶点出队的顺序加上从队头开始队中剩下的顶点。

代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 1e5 + 10;
int n, m, idx;
int heads[N], vals[N], nexts[N], ind[N];
int que[N], hh, tt = -1;

void add(int a, int b) {
    vals[idx] = b;
    nexts[idx] = heads[a];
    heads[a] = idx++;
}

bool top_sort() {
    for (int i = 1; i <= n; ++i) {
        if (!ind[i]) que[++tt] = i;
    }
    while (hh <= tt) {
        int curr = que[hh++];
        for (int i = heads[curr]; i != -1; i = nexts[i]) {
            int j = vals[i];
            if (--ind[j] == 0) que[++tt] = j; 
        }
    }
    return tt == n - 1;
}

int main() {
    memset(heads, -1, sizeof(heads));
    scanf("%d%d", &n, &m);
    while (m--) {
        int a, b;
        scanf("%d%d", &a, &b);
        add(a, b);
        ++ind[b];
    }
    if (top_sort()) {
        for (int i = 0; i < n; ++i) printf("%d ", que[i]);
    } else puts("-1");
    
    return 0;
}

import java.util.*;
import java.io.*;

public class Main {
    static int[] heads, vals, nexts, ind;
    static boolean[] vis;
    static int n, m, idx;
    static int[] que;
    static int hh, tt = -1;
    
    static void add(int a, int b) {
        vals[idx] = b;
        nexts[idx] = heads[a];
        heads[a] = idx++;
    }
    
    static boolean topSort() {
        que = new int[n + 1];
        for (int i = 1; i <= n; ++i) {
            if (ind[i] == 0) que[++tt] = i;
        }
        while (hh <= tt) {
            int curr = que[hh++];
            for (int i = heads[curr]; i != -1; i = nexts[i]) {
                int j = vals[i];
                if (--ind[j] == 0) que[++tt] = j;
            }
        }
        return tt == n - 1;
    }
    
    public static void main(String[] args) throws IOException {
        StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        in.nextToken();
        n = (int) in.nval;
        in.nextToken();
        m = (int) in.nval;
        heads = new int[n + 1];
        Arrays.fill(heads, -1);
        vals = new int[m + 1];
        nexts = new int[m + 1];
        ind = new int[n + 1];
        vis = new boolean[n + 1];
        for (int i = 0; i < m; ++i) {
            in.nextToken();
            int a = (int) in.nval;
            in.nextToken();
            int b = (int) in.nval;
            add(a, b);
            ++ind[b];
        }
        if (topSort()) {
            for (int i = 0; i < n; ++i) {
                System.out.print(que[i] + " ");
            }
        } else System.out.println("-1");
    }
}

目录CONTENT

【BFS】有向图的拓扑序列

题目

解题

方法一：BFS

思路

代码

评论区