当前位置: 代码迷 >> 综合 >> uva10305--拓扑
  详细解决方案

uva10305--拓扑

热度:80   发布时间:2023-11-06 19:28:47.0

题意:

对于给定的关系,输出可能的序列,就是拓扑排序。

输入结束的标志并不是0&& 0,而是0||0,这是一个坑;

#include<iostream>
#include<cstring>
using namespace std;
int c[105],out[105];
int ma[105][105];
int m,n,t;
bool dfs(int u){c[u]=-1;for(int i=1;i<=n;i++)if(ma[u][i]) {if(c[i]<0) return false;if(!c[i]&&!dfs(i)) return false;}	c[u]=1;out[--t]=u;return true;
}
bool ju(){t=n;memset(c,0,sizeof(c)); for(int i=1;i<=n;i++)if(!c[i])if(!dfs(i)) return false;return true; }
int main(){int a,b;while(cin>>n>>m&& (n || m )){memset(ma,0,sizeof(ma));for(int i=0;i<m;i++){cin>>a>>b;ma[a][b]=1;}ju();int flag=0;for(int te=0;te<n;te++){if(flag++) cout<<' ';cout<<out[te];}cout<<endl;}return 0;
}