| ||||||||||
| 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