算法学习-图的存储方式和拓扑排序（JAVA实现）

本文最后更新于：January 27, 2022 pm

纸上得来终觉浅，绝知此事要躬行。路漫漫其修远兮，吾将上下而求索！知识是经过历史的巨人沉淀下来的，别总想着自己能够快速学会，多花点时间去看看，也许会发现些不同的东西。你能快速学会的、觉得简单的东西，对于别人来说也是一样的。人外有人，天外有天。当努力到达了一定的程度，幸运自会与你不期而遇。

目录

图的存储方式这里介绍三种：邻接矩阵、临接表、链式前向星。

邻接矩阵

这是最简单的，就是用二维数组实现。例如：G[a][b] = c；表示 a 点到 b 点之间的边的权重为 c 。

示例：

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
package acmtest;

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


/**
 * @Author DragonOne
 * @Date 2021/12/11 07:13
 * @墨水记忆 www.tothefor.com
 */

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    
    public static int maxd = 1000+7;
    
	public static void main(String[] args) throws Exception {
		
		int[][] G = new int[maxd][maxd];
		int n = nextInt(); //n个点
		int m = nextInt(); //m条边
		while(m-->0) {
			int a = nextInt(); //a点（起点）
			int b = nextInt(); //b点（终点）
			int c = nextInt(); //边的权重
			
			//有向图
//			G[a][b] = c; //a->b
			
			// 无向图
			G[a][b] = c; //a->b
			G[b][a] = c; //b->a
			
		}
		for(int i=1;i<=n;++i) {
			for(int j=1;j<=n;++j) {
				System.out.print(G[i][j]);
			}
			System.out.println();
		}
		
		
		closeAll();
		
	}


	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}


//样例
4 4
1 2 7
1 3 7
2 4 7
1 3 7
    
//输出
0770
7007
7000
0700

临接表

在C++中有一个STL容器叫作Vector，Java中也有，因为是线程安全的，所以效率低。而且也已经被弃用了。

Vector实现（不推荐，知道即可）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
package acmtest;

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


/**
 * @Author DragonOne
 * @Date 2021/12/11 07:13
 * @墨水记忆 www.tothefor.com
 */

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    
    public static int maxd = 1000+7;
    
	public static void main(String[] args) throws Exception {
		int n = nextInt(); //n个点
		int m = nextInt(); //m条边
		Vector<Integer>[] v = new Vector[maxd];
		for(int i=1;i<=n;++i) {
			v[i]= new Vector<>(); 
		}
		while(m-->0) {
			int a = nextInt(); //a点（起点）
			int b = nextInt(); //b点（终点）
			v[a].add(b);
			v[b].add(a);
		}
		for(int i=1;i<=n;++i) {
			int len = v[i].size();
			System.out.print(i+" ");
			for(int j=0;j<len;++j) {
				System.out.print("-> "+v[i].get(j));
			}
			System.out.println();
		}
		
		closeAll();
		
	}
	
	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}


//样例
4 4
1 4
1 2
2 4
2 3

//输出
1 -> 4-> 2
2 -> 1-> 4-> 3
3 -> 2
4 -> 1-> 2

ArrayList实现

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
package acmtest;

import java.awt.List;
import java.io.*;
import java.util.*;

import com.sun.xml.internal.messaging.saaj.packaging.mime.util.LineInputStream;


/**
 * @Author DragonOne
 * @Date 2021/12/11 07:13
 * @墨水记忆 www.tothefor.com
 */

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    
    public static int maxd = 1000+7;
    
	public static void main(String[] args) throws Exception {
		int n = nextInt(); //n个点
		int m = nextInt(); //m条边
		ArrayList[] list = new ArrayList[maxd];
		for(int i=1;i<=n;++i) {
			list[i]= new ArrayList<Integer>();
		}
		while(m-->0) {
			int a = nextInt(); //a点（起点）
			int b = nextInt(); //b点（终点）
			list[a].add(b);
			list[b].add(a);
		}
		for(int i=1;i<=n;++i) {
			int len = list[i].size();
			System.out.print(i+" ");
			for(int j=0;j<len;++j) {
				System.out.print(" -> "+list[i].get(j));
			}
			System.out.println();
		}
		
		closeAll();
		
	}
	


	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

//样例
4 4
1 4
1 3
2 3
2 4

//输出
1  -> 4 -> 3
2  -> 3 -> 4
3  -> 1 -> 2
4  -> 1 -> 2

LinkedList实现

同ArrayList实现一样的道理。只是把ArrayList改成LinkedList即可。不再演示。

链式前向星

实现的效果同临接表一样（存储方式也可以理解成临接表）。只不过是通过数组实现的。

用不同的方式实现链式前向星，本质一样，只是在增加边信息（add_edge()方法）的实现方式不同。

方式一（Setter/Getter方法）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
package acmtest;

import java.awt.List;
import java.io.*;
import java.util.*;

import com.sun.xml.internal.messaging.saaj.packaging.mime.util.LineInputStream;


/**
 * @Author DragonOne
 * @Date 2021/12/11 07:13
 * @墨水记忆 www.tothefor.com
 */

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    
    public static int maxd = 1000+7;
    
    public static class Edge{
    	 private int pre; // pre表示与这条边同起点的上一条边所在结点的编号
    	 private int to; // to表示这条边的终点
    	 private int w; //表示边的权重
  
		public int getPre() {
			return pre;
		}
		public void setPre(int pre) {
			this.pre = pre;
		}
		public int getTo() {
			return to;
		}
		public void setTo(int to) {
			this.to = to;
		}
		public int getW() {
			return w;
		}
		public void setW(int w) {
			this.w = w;
		}
		
    }
    
    public static int node; //边的编号
    public static int[] head = new int[maxd]; //点集 head[i]表示以i为起点的最后一条边所在结点的编号
    public static Edge[] edge = new Edge[maxd]; //存储边信息
    //初始化
    public static void init() {
    	Arrays.fill(head, -1); //-1表示没有边
    	node = 0;
    }
    //增加边信息,a点到b点的边权重为w
    public static void add_edge(int a,int b,int w) {
    	edge[node]= new Edge(); //来一个声明一个
    	edge[node].setTo(b);
    	edge[node].setW(w);
    	edge[node].setPre(head[a]);
    	head[a]=node++;
    }
    
	public static void main(String[] args) throws Exception {
		int n = nextInt(); //n个点
		int m = nextInt(); //m条边
		init();
		while(m-->0) {
			int a = nextInt(); //a点（起点）
			int b = nextInt(); //b点（终点）
			int c = nextInt(); //边的权重
			//有向图
//			add_edge(a, b, c); //a->b
			
			//无向图
			add_edge(a, b, c); //a->b
			add_edge(b, a, c); //b->a
		}
		for(int i=1;i<=n;++i) {
			System.out.print(i+" ");
			for(int j=head[i];j!=-1;j=edge[j].getPre()) { //不断寻找当前点的上一条边，没有边（为-1时）则结束
				System.out.print(" -> "+edge[j].getTo());
			}
			System.out.println();
		}
		
		closeAll();
		
	}
	

	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}


//样例
4 4
1 4 7
1 3 7
2 4 7
3 4 7
    
//输出
1  -> 3 -> 4
2  -> 4
3  -> 4 -> 1
4  -> 3 -> 2 -> 1

此方式还有一种实现方法，在init()方法中进行，上面的代码是在增加一条边的时候才声明一条边，现在就可以一次性把需要的边声明完。只是在声明的时候需要注意是无向图还是有向图。（边数相差两倍）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
package acmtest;

import java.awt.List;
import java.io.*;
import java.util.*;

import com.sun.xml.internal.messaging.saaj.packaging.mime.util.LineInputStream;


/**
 * @Author DragonOne
 * @Date 2021/12/11 07:13
 * @墨水记忆 www.tothefor.com
 */

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    
    public static int maxd = 1000+7;
    
    public static class Edge{
    	 private int pre; // pre表示与这条边同起点的上一条边所在结点的编号
    	 private int to; // to表示这条边的终点
    	 private int w; //表示边的权重
  
		public int getPre() {
			return pre;
		}
		public void setPre(int pre) {
			this.pre = pre;
		}
		public int getTo() {
			return to;
		}
		public void setTo(int to) {
			this.to = to;
		}
		public int getW() {
			return w;
		}
		public void setW(int w) {
			this.w = w;
		}
		
    	 
    }
    public static int node; //边的编号
    public static int[] head = new int[maxd]; //点集 head[i]表示以i为起点的最后一条边所在结点的编号
    public static Edge[] edge = new Edge[maxd]; //存储边信息
    //初始化
    public static void init(int m) {
    	Arrays.fill(head, -1); //-1表示没有边
    	for(int i=0;i<=m*2;++i) { //这里是无向图，所以边数要乘2。必须要从0开始，因为边的编号是从0开始的，即node是从0开始的
    		edge[i] = new Edge();
    	}
    	node = 0;
    }
    //增加边信息,a点到b点的边权重为w
    public static void add_edge(int a,int b,int w) {
    	edge[node].setTo(b);
    	edge[node].setW(w);
    	edge[node].setPre(head[a]);
    	head[a]=node++;
    }
    
	public static void main(String[] args) throws Exception {
		int n = nextInt(); //n个点
		int m = nextInt(); //m条边
		init(m);
		while(m-->0) {
			int a = nextInt(); //a点（起点）
			int b = nextInt(); //b点（终点）
			int c = nextInt(); //边的权重
			//有向图
//			add_edge(a, b, c); //a->b
			
			//无向图
			add_edge(a, b, c); //a->b
			add_edge(b, a, c); //b->a
		}
		for(int i=1;i<=n;++i) {
			System.out.print(i+" ");
			for(int j=head[i];j!=-1;j=edge[j].getPre()) { //不断寻找当前点的上一条边，没有边（为-1时）则结束
				System.out.print(" -> "+edge[j].getTo());
			}
			System.out.println();
		}
		
		closeAll();
		
	}
	

	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

方式二（构造函数）

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
package acmtest;

import java.awt.List;
import java.io.*;
import java.util.*;

import com.sun.xml.internal.messaging.saaj.packaging.mime.util.LineInputStream;


/**
 * @Author DragonOne
 * @Date 2021/12/11 07:13
 * @墨水记忆 www.tothefor.com
 */

public class Main {
	public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);
    
    public static int maxd = 1000+7;
    
    public static class Edge{
    	 private int pre; // pre表示与这条边同起点的上一条边所在结点的编号
    	 private int to; // to表示这条边的终点
    	 private int w; //表示边的权重
    	 
    	public Edge() {}
    	public Edge(int pre,int to,int w) {
			this.pre= pre;
			this.to= to;
			this.w= w;
		}
		public int getPre() {
			return pre;
		}
		public void setPre(int pre) {
			this.pre = pre;
		}
		public int getTo() {
			return to;
		}
		public void setTo(int to) {
			this.to = to;
		}
		public int getW() {
			return w;
		}
		public void setW(int w) {
			this.w = w;
		}
		
    	 
    }
    public static int node; //边的编号
    public static int[] head = new int[maxd]; //点集 head[i]表示以i为起点的最后一条边所在结点的编号
    public static Edge[] edge = new Edge[maxd]; //存储边信息
    //初始化
    public static void init() {
    	Arrays.fill(head, -1); //-1表示没有边
    	node = 0;
    }
    //增加边信息,a点到b点的边权重为w
    public static void add_edge(int a,int b,int w) {
    	edge[node]= new Edge(head[a],b,w); 
    	head[a]=node++;
    }
    
	public static void main(String[] args) throws Exception {
		int n = nextInt(); //n个点
		int m = nextInt(); //m条边
		init();
		while(m-->0) {
			int a = nextInt(); //a点（起点）
			int b = nextInt(); //b点（终点）
			int c = nextInt(); //边的权重
			//有向图
//			add_edge(a, b, c); //a->b
			
			//无向图
			add_edge(a, b, c); //a->b
			add_edge(b, a, c); //b->a
		}
		for(int i=1;i<=n;++i) {
			System.out.print(i+" ");
			for(int j=head[i];j!=-1;j=edge[j].getPre()) { //不断寻找当前点的上一条边，没有边（为-1时）则结束
				System.out.print(" -> "+edge[j].getTo());
			}
			System.out.println();
		}
		
		closeAll();
		
	}
	

	public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

//样例
4 4
1 4 7
1 3 7
2 4 7
3 4 7
    
//输出
1  -> 3 -> 4
2  -> 4
3  -> 4 -> 1
4  -> 3 -> 2 -> 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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
import java.io.*;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 100000+7;
    public static int INF = 0x3f3f3f3f;
    public static int[] head = new int[maxd];
    public static int[] edgePre = new int[maxd]; //上一条边的编号
    public static int[] edgeW = new int[maxd]; //权重
    public static int[] edgeTo = new int[maxd]; //终点
    public static int[] dis = new int[maxd]; //最短距离
    public static boolean[] vis= new boolean[maxd];
    public static int node = 0;
    //初始化
    public static void init(int n,int m){ //n个点，m条边
        for(int i=1;i<=n;++i) {
            head[i]=-1;
            dis[i]=INF;
            vis[i]=false;
        }
        node=0;
    }
    public static void add_edge(int a,int b,int c){ //a到b的权值为c
        edgeTo[node]=b;
        edgeW[node]=c;
        edgePre[node]=head[a];
        head[a]=node++;
    }
    
    public static void main(String[] args) throws Exception {

        int n = nextInt(); //n个点，m条边
        int m = nextInt();
        init(n,m);
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            int c = nextInt();
            add_edge(a,b,c); //可以用于重边不同权的情况
        }
        cout.println();
        cout.flush();

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers(); //可单独使用来还原数字
    }

    public static int nextInt() throws Exception{
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception{
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception{
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception{
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }

}

拓扑排序

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
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;


/**
 * @Author DragonOne
 * @Date 2021/12/5 21:27
 * @墨水记忆 www.tothefor.com
 */
public class Main {
    public static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    public static BufferedWriter out = new BufferedWriter(new OutputStreamWriter(System.out));
    public static StreamTokenizer cin = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
    public static PrintWriter cout = new PrintWriter(new OutputStreamWriter(System.out));
    public static Scanner sc = new Scanner(System.in);

    public static int maxd = 10000+7;
    public static int INF = 0x3f3f3f3f;
    public static int mod = 998244353;
    public static int[] head = new int[maxd];
    public static int[] edgePre = new int[maxd]; //上一条边的编号
    public static int[] edgeTo = new int[maxd]; //终点
    public static int[] num = new int[maxd]; //记录度数
    public static int node = 0;
    public static PriorityQueue<Integer> q = new PriorityQueue<>();
    public static Queue<Integer> v = new ArrayDeque<>();

    //初始化
    public static void init(int n,int m){ //n个点，m条边
        for(int i=1;i<=n;++i) {
            head[i]=-1;
        }
        node=0;
    }
    public static void add_edge(int a,int b){ //a到b
        edgeTo[node]=b;
        edgePre[node]=head[a];
        head[a]=node++;
    }
    public static void topo(int n){
        for(int i=1;i<=n;++i){
            if(num[i]==0) q.add(i);
        }
        while(!q.isEmpty()){
            int now = q.poll();
            v.add(now);
            for(int i=head[now];i!=-1;i=edgePre[i]){
                int to = edgeTo[i];
                num[to]--;
                if(num[to]==0) q.add(to);
            }
        }
        int len = v.size();
        if(len==n){
            for(int i=0;i<len;++i){
                System.out.print(v.poll()+" ");
            }
        }else {
            System.out.println("NO");
        }
    }

    public static void main(String[] args) throws Exception {

        int n = nextInt(); //n个点，m条边
        int m = nextInt();
        init(n,m);
        for(int i=1;i<=m;++i){
            int a = nextInt();
            int b = nextInt();
            add_edge(a,b); //a->b
            num[b]++;
        }
        topo(n);

        closeAll();
    }

    public static void cinInit(){
        cin.wordChars('a', 'z');
        cin.wordChars('A', 'Z');
        cin.wordChars(128 + 32, 255);
        cin.whitespaceChars(0, ' ');
        cin.commentChar('/');
        cin.quoteChar('"');
        cin.quoteChar('\'');
        cin.parseNumbers();
    }
    public static int log(int x){ //log方法是以2为底,求x的对数。java自带的log是以e为底的
        return (int) (Math.log(x)/Math.log(2));
    }
    public static int nextInt() throws Exception {
        cin.nextToken();
        return (int) cin.nval;
    }
    public static long nextLong() throws Exception {
        cin.nextToken();
        return (long) cin.nval;
    }
    public static double nextDouble() throws Exception {
        cin.nextToken();
        return cin.nval;
    }
    public static String nextString() throws Exception {
        cin.nextToken();
        return cin.sval;
    }
    public static void closeAll() throws Exception {
        cout.close();
        in.close();
        out.close();
    }
}

测试数据

输入：

1
2
3
4
5
6
7
8
9
6 8
1 2
1 3
1 4
3 2
3 5
4 5
6 4
6 5

输出：

1
1 3 2 6 4 5
算法学习
ACM 算法

本文作者: 墨水记忆
本文链接: https://tothefor.com/DragonOne/b5bae460.html
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！