hdu 1269 (tarjan)

2726 ワード
迷宮の城
Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 6740    Accepted Submission(s): 3014
Problem Description
希ちゃんの方向感覚を訓練するために、Gardonは大きな城を建てました.中にはN部屋(N<=10000)とM通路(M<=10000)があり、各通路は一方向です.つまり、ある通路がA部屋とB部屋につながっているとすれば、この通路を通ってA部屋からB部屋に着くことができることを説明するだけですが、B部屋からA部屋に着くことは説明しません.Gardonは、任意のiとjに対して、少なくとも1つの経路が部屋iから部屋jまで、1つの経路が部屋jから部屋iまでつながっているかどうかを確認するプログラムを書く必要があります.
 
Input
入力には複数のデータのセットが含まれ、入力された最初の行にはNとMの2つの数があり、次のM行には1行あたり2つの数aとbがあり、1つのチャネルがA部屋からB部屋に来ることができることを示している.ファイルは最後に2つの0で終了します.
 
Output
入力された各グループのデータについて、いずれの部屋も互いに接続されている場合は「Yes」を出力し、そうでない場合は「No」を出力します.
 
Sample Input 

   
   
   
   

    
    
    
    3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0

 
Sample Output 

   
   
   
   

    
    
    
    Yes
No

 
Author
Gardon
 
Source
HDU 2006-4 Programming Contest
 
分析:裸強連通図、
tarjanコード:(tarjanは1つのdfsツリー上の連通成分数しかスキャンできません.同じ連通サブマップrootノードをすべて集約することで、最後に遍歴しても解けます)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10500;
const int MAXM=100500;
int first[MAXN],low[MAXN],dfn[MAXN],inq[MAXN],done[MAXN],st[MAXN],root[MAXN];
int next[MAXM],u[MAXM],v[MAXM];
int cnt,scnt,top,sccnt;

void dfs(int cur)
{
	int e;
	dfn[cur]=low[cur]=scnt++;
	inq[cur]=1;
	done[cur]=0;
	st[top++]=cur;
	for(e=first[cur];e!=-1;e=next[e])
		if(!inq[v[e]])//white
		{
			dfs(v[e]);
			if(low[cur]>low[v[e]])low[cur]=low[v[e]];
		}
  		else if(!done[v[e]]&&dfn[v[e]]<low[cur])//grep
				low[cur]=dfn[v[e]];
	if(low[cur]==dfn[cur])
	{
		do
		{
			root[st[--top]]=cur;
			done[st[top]]=1;
		}while(st[top]!=cur);
		sccnt++;
	}
}
void add_ded(int a,int b)
{
	u[cnt]=a;
	v[cnt]=b;
	next[cnt]=first[a];
	first[a]=cnt++;
}
int main()
{
	//freopen("123.txt","r",stdin);
	int n,m,i,s,t;
	while(~scanf("%d%d",&n,&m))
	{
		if(!n&&!m)break;
		cnt=0;top=0;scnt=sccnt=0;
		memset(first,-1,sizeof first);
		memset(next,-1,sizeof next);
		memset(done,0,sizeof done);
		memset(inq,0,sizeof inq);
		memset(root,-1,sizeof root);
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&s,&t);
			add_ded(s,t);
		}
		dfs(1);
		for(i=1;i<=n;i++)
			if(root[i]!=1){sccnt=2;break;}
		if(sccnt==1)printf("Yes
");
		else printf("No
");
	}
	return 0;
}
汎用的な運用
文字列がサブストリングループから得られるかどうか-java