hdu 3342 Legal or Not(给一个有向图判断该图是否拓扑有序)
分类:Graph Theory–Topological Sort
topology
代码:#include<cstdio>#include<cstring>using namespace std;int n,m;int mat[105][105];int in[105];int Stack[105],top;void topo(){top=0;for(int i=0; i<n; i++){if(in[i]==0){Stack[++top]=i;in[i]=-1;}}int cnt=0;while(top!=0){int j=Stack[top–];cnt++;for(int i=0; i<n; i++){if(mat[j][i]){in[i]-=(mat[j][i]);}if(in[i]==0){Stack[++top]=i;in[i]=-1;}}}if(cnt==n)printf("YES\n");elseprintf("NO\n");}int main(){while(scanf("%d%d",&n,&m)&&(n||m)){memset(mat,0,sizeof(mat));memset(in,0,sizeof(in));for(int i=0; i<m; i++){int a,b;scanf("%d%d",&a,&b);mat[a][b]++;in[b]++;}topo();}return 0;}
版权声明:本文为博主原创文章,,未经博主允许不得转载。
上一篇hdu 1285 确定比赛名次(给一个拓扑有序图要求输出拓扑有序序列)下一篇scanf("%s",s);语句输入
顶0踩0
别人失去了信心,他却下决心实现自己的目标。