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

小菜求DEBUG 先求强连通分量 在对每个连通分量中的点处理 如果有一个点的出度指向其他连通分量 则此连通分量中的点都不是SINK 思路不对么?

Posted by mopishv1 at 2008-11-01 20:32:30 on Problem 2553
#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:
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