AcWing.848- 有向图的拓扑序列（java实现）

62 阅读 0 评论 41 点赞

我是靠谱客的博主伶俐黄豆，最近开发中收集的这篇文章主要介绍AcWing.848- 有向图的拓扑序列（java实现），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

AcWing.848- 有向图的拓扑序列

题目描述

给定一个 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

输入样例：

输出样例：

1 2 3

题解

package acWing848;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class Main {
	static int N = 100010;
	static int n,m;
	static int h[] = new int[N],e[] = new int[N],ne[] = new int[N],idx;
	static int in[] = new int[N],q[] = new int[N];
	static void add(int a,int b) {
		e[idx] = b;
		ne[idx] = h[a];
		h[a] = idx++;
	}
	static boolean topsort() {
		int hh=0,tt =-1;
		for(int i=1;i<=n;i++) {
			if(in[i]==0) {
				q[++tt] = i;
			}
		}
		while(hh<=tt) {
			int t = q[hh++];
			for(int i=h[t];i!=-1;i=ne[i]) {
				int j = e[i];
				in[j]--;
				if(in[j]==0) {
					q[++tt] = j;
				}
			}
		}
		return tt==n-1;
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String str[] = bf.readLine().split(" ");
		Arrays.fill(h, -1);
		n = Integer.parseInt(str[0]);m = Integer.parseInt(str[1]);
		for(int i=0;i<m;i++) {
			str = bf.readLine().split(" ");
			int a = Integer.parseInt(str[0]),b = Integer.parseInt(str[1]);
			add(a,b);
			in[b]++;
		}
		if(topsort()) {
			for(int i=0;i<n;i++) {
				System.out.print(q[i]+" ");
			}
		}else{
			System.out.println(-1);
		}
	}
}