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 |
小菜求DEBUG 先求强连通分量 在对每个连通分量中的点处理 如果有一个点的出度指向其他连通分量 则此连通分量中的点都不是SINK 思路不对么?#include<iostream> #include<vector> using namespace std; const int N=5100; class Graph { private: vector<int> g[N]; int n,m,h[N],id[N],sign[N]; int cnt,scnt,dfn[N],low[N],cur[N],cur2[N]; int stack[N],top,est[N],etop; void dfs(int); void init(); public: bool build(); void scR(); }; void Graph::init() { for(int i=0;i<=n+1;i++) { g[i].clear(); dfn[i]=-1; h[i]=id[i]=sign[i]=low[i]=cur[i]=cur2[i]=0; } cnt=scnt=top=etop=0; } bool Graph::build() { if(scanf("%d",&n)==EOF) return false; if(n==0) return false; scanf("%d",&m); init(); for(int i=0;i<m;i++) { int s,e; scanf("%d%d",&s,&e); s--,e--; g[s].push_back(e); } } void Graph::scR() { for(int i=0;i<n;i++) cur2[i]=cur[i]=g[i].size()-1; for(int i=0;i<n;i++) //非递归TARJAN求强连通分量 { if(dfn[i]==-1) dfs(i); } for(int i=0;i<n;i++) //如果连通分量中有点指向其他连通分量 则该连通分量中的点不是sink { for(int j=0;j<=cur2[i]&&sign[id[i]]==0;j++) { if(id[i]!=id[g[i][j]]) sign[id[i]]=1; } } int k=0; for(int i=0;i<n;i++) { if(sign[id[i]]==0) { if(k==0) { printf("%d",i+1); k++; } else printf(" %d",i+1); } } printf("\n"); } void Graph::dfs(int src) { top=etop=0; stack[top]=src,top++; while(top!=0) { int c=stack[top-1]; if(dfn[c]==-1) h[c]=dfn[c]=low[c]=cnt,cnt++,est[etop]=c,etop++; for(;cur[c]>=0;cur[c]--) { int no=g[c][cur[c]]; if(dfn[no]==-1) { stack[top]=no,top++; break; } h[c]<?=low[no]; } if(cur[c]>=0) continue; top--; int k; if(h[c]!=low[c]) { low[c]=h[c]; continue; } do { etop--,k=est[etop]; id[k]=scnt,low[k]=N; }while(k!=c); scnt++; } } int main() { //freopen("2039.in","r",stdin); //freopen("test.out","w",stdout); Graph graph; while(graph.build()) graph.scR(); return 0; } Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator