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

86 阅读 0 评论 57 点赞

我是靠谱客的博主伶俐黄豆，这篇文章主要介绍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
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);
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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);
		}
	}
}