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 |
Tarjan缩点后找出度为0的强连通分量排序输出,特殊情况是强连通分量数为1直接输出1...n#include <algorithm> #include <iostream> #include <fstream> #include <sstream> #include <iomanip> #include <map> #include <set> #include <list> #include <stack> #include <queue> #include <deque> #include <vector> #include <string> #include <bitset> #include <complex> #include <memory> #include <numeric> #include <stdio.h> #include <stdlib.h> #include <string.h> #include <math.h> #include <time.h> #include <ctype.h> #include <locale.h> using namespace std; const int inf = 0x7f7f7f7f; const int INF = 0x7fffffff; const double eps = 1e-8; const double pi = acos(-1.0); #define _at(a,i) ((a)&(1<<(i))) #define _not(a,i) ((a)^(1<<(i))) #define _st1(a,i) ((a)|(1<<(i))) #define _st0(a,i) ((a)&~(1<<(i))) #define _lowbit(val) ((val)&(-val)) #define _gret(a,b) ((a)-(b)>eps) #define _less(a,b) ((b)-(a)>eps) #define _equl(a,b) (fabs((a)-(b))<eps) #define _sign(a) (_gret(a,0.0)?1:(_equl(a,0.0)?0:-1)) #define _max(a,b) (_gret(a,b)?(a):(b)) #define _min(a,b) (_less(a,b)?(a):(b)) #define _for(i,a,b) for(int i=(a);i<=(b);i++) #define _clr(a,val,n) memset(a,val,sizeof(a[0])*(n)) #define _Constant_ typedef int EleType; const int MAXV = 52000; const int MAXE = 52000; #define _AdjList_ struct node { int v; EleType w; }G[MAXE]; int index,pre[MAXV],next[MAXE]; void clear(void) { index=0; _clr(pre,-1,MAXV); _clr(next,-1,MAXE); } void add(int u,int v,EleType w) { G[index].v=v; G[index].w=w; next[index]=pre[u]; pre[u]=index++; } #define _Variable_ set<int> Q; int n,m,u,v,out[MAXV]; bool vis[MAXE]; int scc,dfn,low[MAXE],dfs[MAXE],stk[MAXE],cnc[MAXV]; #define _Tarjan_ void Tour(int u) { vis[u]=true; stk[++stk[0]]=u; low[u]=dfs[u]=++dfn; for(int i=pre[u];i!=-1;i=next[i]) { if(!vis[G[i].v]) { Tour(G[i].v); low[u]=min(low[u],low[G[i].v]); } else if(!cnc[G[i].v]) low[u]=min(low[u],low[G[i].v]); } if(low[u]==dfs[u]) { scc++; do { cnc[stk[stk[0]]]=scc; } while(stk[stk[0]--]!=u); } } int Tarjan(void) { scc=dfn=stk[0]=0; _clr(cnc,0,MAXV); _clr(vis,false,MAXV); _for(i,0,n-1) if(!vis[i]) Tour(i); return scc; } #define _Recution void redution(void) { Q.clear(); _clr(out,0,MAXV); _for(i,0,n-1) for(int j=pre[i];j!=-1;j=next[j]) { if(cnc[i]!=cnc[G[j].v]) out[cnc[i]-1]++; } _for(i,0,scc-1) if(!out[i]) { _for(j,0,n-1) if(cnc[j]-1==i) { Q.insert(j+1); } } if(!Q.empty()) { set<int>::iterator i=Q.begin(); printf("%d",*i); for(i++;i!=Q.end();i++) printf(" %d",*i); } printf("\n"); } int main() { while(scanf("%d",&n),n) { scanf("%d",&m); clear(); _for(i,0,m-1) { scanf("%d %d",&u,&v); add(u-1,v-1,1); } Tarjan(); redution(); } return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator