HD1285(拓扑排序）

package cn.hncu.dataStruct.search.topSort;

import java.util.Scanner;

public class Hdu1285 {
static Scanner sc = new Scanner(System.in);
static int n,m;
static int arc[][];//邻接矩阵，0不存在边，1存在边
static int sorted[];//表示是否已经排过序
static int degree[];//入度

public static void main(String[] args) {
while(sc.hasNext()){
n = sc.nextInt();
m = sc.nextInt();
init();//输入并初始化图
topSort();
}
}

private static void init() {
sorted = new int[n];
degree = new int[n];
arc = new int[n][n];//邻接矩阵，代表n个节点之间的有向边,0表示没有边
//初始化
for(int i=0;i<n;i++){
sorted[i] = 0;//未排序
degree[i] = 0;//每个节点的入度初始化为0
for(int j=0;j<n;j++){
arc[i][j]=0;
}
}

//图的输入---比赛胜负关系的输入
for(int i=0;i<m; i++){
int a = sc.nextInt()-1;
int b = sc.nextInt()-1;
if(arc[a][b]==0){//防止出现重边---把重边过滤掉
arc[a][b] = 1;
degree[b]++;
}
}
}

private static void topSort() {
int s = 0;//已经排序的节点个数
while(s<n){
int i=0;
for( i=0;i<n;i++){
if(degree[i]==0 && sorted[i]==0){//入度为0且还没有排序
break;
}
}
if(i==n){//已经没有节点可排了
System.out.println("图中存在回路，题目无解!");
return;
}
sorted[i]=1;//标记已排过
s++;
System.out.print(i+1);
if(s<n){
System.out.print(" ");
}else{
System.out.println();
}
//把以i为起点j为终点的那些边消掉---degree[j]-1
for(int j=0;j<n;j++){
if(arc[i][j]==1){
//arc[i][j]=0;//在矩阵上消边
degree[j]--;
}
}
}
}
}

巴特西

HD1285(拓扑排序）

最新文章

热门文章