hdu 3639 (강 한 연결 점 + 검색)

통계 적 으로 가장 많은 표를 얻 은 사람 은 투표 가 전달 성 을 가진다. a - > b - > c, c 는 두 표를 얻 었 다. 처음에 반 도 를 만 들 려 면 모든 입 도 를 0 으로 하 는 점 (가장 큰 것 은 입 도 를 0 으로 하 는 점) 을 직접 검색 하면 답 이 나온다. 코드 를 반 쯤 두 드 려 서 야 한 가지 문제 가 생각 났 다. 몇 사람 이 투표 해서 하나의 고 리 를 만 들 면 해결 하기 어렵다.
만약 에 i 개인 이 하나의 고 리 를 형성한다 면 모든 사람 이 i - 1 표 이 고 고리 사이 에 연락 이 있 을 수 있 습 니 다.
분명히 강 한 연결 점 문제 입 니 다. 링 을 점 으로 축소 한 다음 에 반 도 를 만들어 직접 검색 하면 ok 입 니 다.

#include<stdio.h>
#include<stack>
#include<string.h>
#define N 5010 
using namespace std;
int n,m;
int dfs[N],low[N],belong[N],ins[N],inq[N],num[N],cont[N],vis[N];
struct edage
{
	int ed;
	struct edage *next;
}*E[N],*e[N];
void addedage(int x,int y)
{
	struct edage *p=new edage;
	p->ed=y;
	p->next=E[x];
	E[x]=p;
}
void Addedage(int x,int y)
{
	struct edage *p=new edage;
	p->ed=y;
	p->next=e[x];
	e[x]=p;
}
stack<int>Q;
int idx,ans;
void Tarjan(int x)
{
	int v;
	dfs[x]=low[x]=idx++;
	Q.push(x);
	ins[x]=1;
	for(edage *j=E[x];j;j=j->next)
	{
		if(dfs[j->ed]==-1)
		{
			Tarjan(j->ed);
			low[x]=low[x]>low[j->ed]?low[j->ed]:low[x];
		}
		else if(ins[j->ed]==1)
			low[x]=low[x]>dfs[j->ed]?dfs[j->ed]:low[x];
	}
	if(low[x]==dfs[x])
	{
		while(1)
		{
			v=Q.top();
			Q.pop();
			ins[v]=0;
			belong[v]=ans;
			num[ans]++;
			if(v==x)break;
		}
		ans++;
	}
}
int DFS(int x)
{
	vis[x]=1;
	int sum=0;
	for(edage *q=e[x];q;q=q->next)
		if(vis[q->ed]==0)
			sum+=(num[q->ed]+DFS(q->ed));
		return sum;
}
int main()
{
	int i,j,x,op=1,t,y;
	scanf("%d",&t);
	while(t--)
	{
		memset(E,NULL,sizeof(E));
		memset(e,NULL,sizeof(e));
		memset(dfs,-1,sizeof(dfs));
		memset(ins,0,sizeof(ins));
		memset(inq,0,sizeof(inq));
		memset(num,0,sizeof(num));
		memset(cont,0,sizeof(cont));
		scanf("%d%d",&n,&m);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&x,&y);
			addedage(x,y);
		}
		idx=ans=0;
		for(i=0;i<n;i++)
		{
			if(dfs[i]==-1)
				Tarjan(i);//  
		}
		for(i=0;i<n;i++)
		{
			for(edage *q=E[i];q;q=q->next)
			{
				if(belong[i]!=belong[q->ed])
				{
					inq[belong[i]]++;
					Addedage(belong[q->ed],belong[i]);//   
				}
			}
		}
		int max=-1;
		for(i=0;i<ans;i++)
		{
			memset(vis,0,sizeof(vis));
			if(inq[i]==0)
			{
				cont[i]=num[i]-1+DFS(i);
				if(max<cont[i])
				{max=cont[i];}
			}
		}
		printf("Case %d: %d
",op++,max);
		for(i=0;i<n;i++)
			if(cont[belong[i]]==max)
				break;
			printf("%d",i++);
			for(;i<n;i++)
				if(cont[belong[i]]==max)
					printf(" %d",i);
				printf("
");
	}
	return 0;
}