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 |
这样的错误程序也能过#include<iostream> using namespace std; #include<vector> #include<stack> #define in(x) scanf("%d",&(x)) int n,m,time,cnt; vector<int> edge[5002]; stack<int> st; bool out[5002]; int low[5002],dfs[5002],scc[5002]; void Dfs(int x) { int i,j,k; dfs[x]=low[x]=time++; st.push(x); for(i=0;i<edge[x].size();i++){ if(!dfs[edge[x][i]]) Dfs(edge[x][i]); low[x]=min(low[edge[x][i]],low[x]); } if(low[x]==dfs[x]){ scc[x]=++cnt; // low[x]=0x7f7f7f7f; while(st.top()!=x){ scc[st.top()]=cnt; // low[st.top()]=0x7f7f7f7f; st.pop(); } st.pop(); } } int main() { int i,j,k,b,e; while(in(n) && n) { time=1;cnt=0; in(m); memset(out,false,sizeof(out)); memset(dfs,false,sizeof(dfs)); memset(scc,false,sizeof(scc)); for(i=0;i<=n;i++) edge[i].clear(); for(i=0;i<m;i++) { in(b);in(e); edge[b].push_back(e); } for(i=1;i<=n;i++) if(!dfs[i]) Dfs(i); for(i=1;i<=n;i++) for(j=0;j<edge[i].size();j++) if(scc[i]!=scc[edge[i][j]]) out[scc[i]]=true; for(i=1;i<=n;i++) if(!out[scc[i]]) printf("%d ",i); printf("\n"); } } 注意:对于出栈的顶点,low值没有做更新,所以作的scc算法应该是错的,但也能ac... Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator