//按拓扑排序排列 不断删除入度为0的节点 #include<iostream> #include<cstring> #include<algorithm> using namespace std; const int N=110; int h[N],e[N],ne[N],idx; int d[N],q[N]; int n,hh=0,tt=-1; void add(int a,int b) //初始化有向图 { e[idx]=b,ne[idx]=h[a],h[a]=idx++; } void pan() //bool { for(int i=1;i<=n;i++) if(!d[i]) q[++tt]=i; //入度为0的节点入队 while(hh<=tt) { int x=q[hh++]; for(int i=h[x];i!=-1;i=ne[i]) { int j=e[i]; d[j]--; if(d[j]==0) q[++tt]=j; } } // return tt==n-1; 如果此图是拓扑排序,那么tt的值=n-1(所有节点均入队) } int main(void) { memset(h,-1,sizeof(h)); cin>>n; for(int i=1;i<=n;i++) { int x; while(cin>>x&&x) { add(i,x); d[x]++; } } pan(); for(int i=0;i<n;i++) cout<<q[i]<<' '; return 0; }
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.9 (C++代码)浏览:551 |
2005年春浙江省计算机等级考试二级C 编程题(2) (C语言代码)浏览:766 |
C语言考试练习题_保留字母 (C语言代码)浏览:632 |
多输入输出练习1 (C语言代码)浏览:1206 |
【矩阵】 (C++代码)浏览:979 |
简单的a+b (C语言代码)浏览:569 |
大神老白 (C语言代码)浏览:631 |
C语言训练-自守数问题 (C语言代码)浏览:785 |
排序算法(选择,插入,冒泡)浏览:866 |
C语言程序设计教程(第三版)课后习题8.1 (C语言代码)浏览:599 |