HDU1285（拓扑排序（模板））

拓扑排序：
思想：1、在有向图中选择一个没有前驱的顶点并且输出
2、从图中删除该节点和所有以它为尾的弧。
重复上述步骤，知道全部顶点都已经输出，或者当前图中不存在无前驱的顶点为止。后面一种情况说明有向图中存在环。
HDU1285：http://acm.hdu.edu.cn/showproblem.php pid=1285
[java]
package D0731;

import java.util.*;

//图谱排序（邻接矩阵实现图存储）
public class HDU1285_2 {

static int n, m;
static int[] indegree;// 顶点的入度
static int[] result;// 保存最后排好序的结果
static int[][] G;// 邻接矩阵存储
static Queue que;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
n = sc.nextInt();
m = sc.nextInt();
G = new int[n + 1][n + 1];
indegree = new int[n + 1];

while (m-- > 0) {
int u = sc.nextInt();
int v = sc.nextInt();
if (G[u][v] == 0) {// 这个条件一定要，否则WA，避免重边的情况比如a b可能出现两次的情况
indegree[v]++;
G[u][v] = 1;
}
}
topsort();
// 输出
System.out.print(result[1]);
for (int i = 2; i <= n; i++) {
System.out.print(" "+result[i]);
}
System.out.println();
}
}

private static void topsort() {
result = new int[n + 1];
que = new PriorityQueue();
int index = 0;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
que.add(i);
}
while (!que.isEmpty()) {
int u = que.poll();
result[++index] = u;
for (int i = 1; i <= n; i++) {
if (G[u][i] == 1) {
indegree[i]--;
if (indegree[i] == 0)
que.add(i);
}
}
}
}

[java]
package D0731;

import java.util.*;

//拓扑排序（使用邻接表实现）
public class HDU1285_3 {

static int n, m;
static int[] indegree;// 顶点的入度
static int[] result;// 保存最后排好序的结果
static List> G;// 邻接表。
static Queue que;

public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
n = sc.nextInt();
m = sc.nextInt();
G = new ArrayList>();
for(int i = 1;i<=n+1;i++)
G.add(new ArrayList());
indegree = new int[n + 1];
while (m-- > 0) {
int u = sc.nextInt();
int v = sc.nextInt();
if (!G.get(u).contains(v)) {// 这个条件一定要，否则WA，避免重边的情况比如a b可能出现两次的情况
indegree[v]++;
G.get(u).add(v);
}
}
topsort();
// 输出
System.out.print(result[1]);
for (int i = 2; i <= n; i++) {
System.out.print(" " + result[i]);
}
System.out.println();
}
}

private static void topsort() {
result = new int[n + 1];
que = new PriorityQueue();
int index = 0;
for (int i = 1; i <= n; i++) {
if (indegree[i] == 0)
que.add(i);
} www.2cto.com
while (!que.isEmpty()) {
int v = que.poll();
result[++index] = v;
for (int i : G.get(v)) {
indegree[i]--;
if (indegree[i] == 0)
que.add(i);
}
}
}

}
作者：lhfight