侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

【BFS】有向图的拓扑序列

GabrielxD
2022-11-11 / 0 评论 / 0 点赞 / 25 阅读 / 998 字 / 正在检测是否收录...

题目

848. 有向图的拓扑序列


给定一个 nn 个点 mm 条边的有向图,点的编号是 11nn,图中可能存在重边和自环。

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

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

输入格式

第一行包含两个整数 nnmm

接下来 mm 行,每行包含两个整数 xxyy,表示存在一条从点 xx 到点 yy 的有向边 (x,y)(x, y)

输出格式

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

否则输出 1-1

数据范围

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

输入样例:

3 3
1 2
2 3
1 3

输出样例:

1 2 3

解题

方法一:BFS

思路

基本概念:

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

实现拓扑排序:

  • 首先比起一般的图,多维护一个所有顶点的入度(ind),在加入边时更新入度。
  • 维护一个队列(que),把所有入度为 00 的点放入队列。
  • 在队列不为空的条件下循环:
    • 从队头取出一个顶点(curr)。
    • 遍历这个顶点(j)的出边,删除 curr -> j 这条边(其实就是把顶点 j 的入度减一) ,如果删完之后 j 的入度为 00,就把 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");
    }
}
0

评论区