Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这样的错误程序也能过

Posted by 00713062 at 2008-08-26 01:15:54 on Problem 2553
#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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator