AcWing 848. 行行注释 java超详细
原题链接
简单
作者:
季之秋
,
2021-01-18 18:28:44
,
所有人可见
,
阅读 403
import java.util.*;
public class Main{
static int[] e,ne,h,g,d;//g是队列,d是入度(有多少个指向这个点)
static int n,m,idx,N=100010;
static class Pair{
Pair(){//初始化数组
e=new int[N*2];
ne=new int[N*2];
d=new int[N*2];
g=new int[N*2];
h=new int[N*2];
Arrays.fill(h,-1);//让h变为-1代表空
}
void add(int a,int b){//a指向b
e[idx]=b;
ne[idx]=h[a];
h[a]=idx++;
}
}
public static void main(String[] args){
Scanner sc=new Scanner(System.in);
n=sc.nextInt();
m=sc.nextInt();
Pair q=new Pair();
for(int i=0;i<m;i++){
int a=sc.nextInt();
int b=sc.nextInt();
q.add(a,b);
d[b]++;//每次b都有多一个a指向他
}
if(judge()){//判断是不是有向拓扑序列
for(int i=0;i<n;i++){
System.out.printf(g[i]+" ");//输出队列中的数,长度刚好是这个有向图的数量
}
}else{
System.out.println(-1);//不是拓扑就输出-1
}
}
static boolean judge(){
int tt=-1,hh=0;//头指针尾指针
for(int i=1;i<=n;i++){//查找图中入度为0的数然后加入队列
if(d[i]==0) g[++tt] = i;
}
while(hh<=tt){//遍历队列
int t=g[hh++];//取出队头
for(int i=h[t];i!=-1;i=ne[i]){//遍历队头指向的值
int j=e[i];//队头指向的值
d[j]--;//删除这个值和队头的连接线,使这个值得入度-1
if(d[j]==0) g[++tt]=j;//如果入度为0的话就是加入队列,此时原本入度为1的值在-1之后加入到入度为0的后面
}
}
return tt==n-1;//判断队列中的值是不是有n个点(因为节点从1-n,所以数量是n-1个节点)
}//如果是的话就说明是拓扑序列
}