首页 > 代码库 > poj3687拓扑排序
poj3687拓扑排序
反向建图
#include <cstdio>#include <cstring>#include <algorithm>#include <climits>#include <string>#include <iostream>#include <map>#include <cstdlib>#include <list>#include <set>#include <queue>#include <stack>using namespace std;const int INF=0xfffffff;int main(){ int n,m,Icase; int vis[300]; int G[300][300]; int in[300]; int topo[300]; while(cin>>Icase){ while(Icase--){ memset(topo,0,sizeof(topo)); memset(G,0,sizeof(G)); memset(vis,0,sizeof(vis)); memset(in,0,sizeof(in)); cin>>n>>m; for(int i=0;i<m;i++){ int a,b; cin>>a>>b; if(!G[a][b]){ in[a]++; G[a][b]=1; } } int flag=1; for(int i=n;i>=1;i--){ int sign; bool t=false; for(int j=1;j<=n;j++){ if(in[j]==0&&!vis[j]){ sign=j; t=true; } } if(!t){ flag=0;break; } // vis[sign]=1; topo[i]=sign; // cout<<topo[i]<<endl;system("pause"); for(int j=1;j<=n;j++){ if(!vis[j]&&G[j][sign]){ in[j]--; } } vis[sign]=1; } if(!flag)cout<<-1<<endl; else{ int a[300]; for(int i=1;i<=n;i++){ a[topo[i]]=i; } for(int i=1;i<=n;i++){ if(i==1) cout<<a[i]; else cout<<" "<<a[i]; } cout<<endl; } } } return 0;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。