Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
AC..#include<cstdio> #include<cstring> using namespace std; struct node { int x,y,next; }a[1300000];int len,first[5100]; int cnt,belong[21000]; int id,dfn[21000],low[21000],b[5100]; int tp,sta[21000]; bool v[21000]; int ru[21000],chu[21000]; void ins(int x,int y) { len++; a[len].x=x; a[len].y=y; a[len].next=first[x]; first[x]=len; } int mymin(int x,int y) { return x>y?y:x; } void dfs(int x) { low[x]=dfn[x]=++id; sta[++tp]=x; v[x]=true; for(int k=first[x];k ;k=a[k].next) { int y=a[k].y; if(dfn[y]==-1) { dfs(y); low[x]=mymin(low[x],low[y]); } else if(v[y]) { low[x]=mymin(low[x],dfn[y]); } } if(low[x]==dfn[x]) { cnt++; int i; do{ i=sta[tp--]; v[i]=false; belong[i]=cnt; }while(i!=x); } } int main() { int cc,n,m,x,y,i; while(scanf("%d",&n)!=EOF) { if(n==0) break; scanf("%d",&m); len=0; memset(first,0,sizeof(first)); for(i=1;i<=m;i++) { scanf("%d%d",&x,&y); ins(x,y); } id=tp=cnt=0; memset(low,0,sizeof(low)); memset(dfn,-1,sizeof(dfn)); memset(belong,0,sizeof(belong)); memset(v,false,sizeof(v)); for(i=1;i<=n;i++) if(dfn[i]==-1) dfs(i); memset(ru,0,sizeof(ru)); memset(chu,0,sizeof(chu)); for(i=1;i<=len;i++) if(belong[ a[i].x ] != belong[ a[i].y ] ) { chu[belong[a[i].x]]++; ru[belong[a[i].y]]++; } int blen=0; for(i=1;i<=n;i++) { if(chu[belong[i]]==0) { b[++blen]=i; } } if(blen==0) printf("\n"); else { for(i=1;i<blen;i++) printf("%d ",b[i]); printf("%d\n",b[blen]); } } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator