首页 > 代码库 > Gym 100801G Graph 拓扑排序
Gym 100801G Graph 拓扑排序
http://codeforces.com/gym/100801/attachments
用set维护一下入度为零的点,每次将当前指针和下一个指针连一条边
写博客只是为了纪念一下第一次用set,还有我逝去的4小时青春
PS.iterator在迭代器中不要xjb改
#include<cstdio>#include<cstdlib>#include<cstring>#include<iostream>#include<algorithm>#include<queue>#include<set>using namespace std;int n,m,k;set<int>s;int f[200000],g[200000];int sum[200000],tot,sedge;struct point { int to,next;}e[10000000];void add(int x,int y){ e[++tot].to=y; e[tot].next=g[x]; g[x]=tot;}int main(){ freopen("graph.in","r",stdin); freopen("graph.out","w",stdout); scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=m;i++) { int x,y; scanf("%d%d",&x,&y); add(x,y); sum[y]++; } for(int i=1;i<=n;i++) { if(sum[i]==0) s.insert(i); }//cout<<"!!!!!!"<<endl; int sk=k; for(int p=1;p<=n;p++) { int flag=1; set<int>::iterator itlast=s.end();itlast--;//cout<<"!!!!!!"<<endl; set<int>::iterator itar; //cout<<*itlast<<endl; for(set<int>::iterator it=s.begin();it!=itlast;it++) {//cout<<"!!!!!!"<<endl; //cout<<*it<<endl; if(f[*it]) { set<int>::iterator tmp=it; tmp++; f[*it]=*tmp; add(*tmp,*it); sum[*it]++; continue; } if(f[*it]==0&&sk>0) { set<int>::iterator tmp=it; tmp++; f[*it]=*tmp; //cout<<*tmp<<" "<<*it<<endl; add(*tmp,*it); sum[*it]++;//cout<<"!!!!!!"<<endl; sk--; continue; } printf("%d ",*it); itar=it; flag=0; break; } if(flag) { set<int>::iterator itlast=s.end();itlast--; printf("%d ",*itlast); int x=*itlast; s.erase(s.begin(),s.find(x)); s.erase(x); for(int temp=g[x];temp;temp=e[temp].next) { sum[e[temp].to]--; if(sum[e[temp].to]==0) s.insert(e[temp].to); } } else { int x=*itar; s.erase(s.begin(),s.find(x)); s.erase(x); for(int temp=g[x];temp;temp=e[temp].next) { sum[e[temp].to]--; if(sum[e[temp].to]==0) s.insert(e[temp].to); } } } int ans=0; for(int i=1;i<=n;i++) { if(f[i])ans++; } cout<<endl<<ans<<endl; for(int i=1;i<=n;i++) if(f[i])printf("%d %d\n",f[i],i); return 0;}
Gym 100801G Graph 拓扑排序
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。