迷宫城堡（强连通分量）

￡神魔★判官ぃ 2022-08-02 05:55 194阅读 0赞

# 迷宫城堡 #

**Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)  
Total Submission(s): 9215    Accepted Submission(s): 4115**

Problem Description

为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。

Input

输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个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][]

**强连通分量的裸题！**

#include<iostream>
    #include<vector>
    #include<cstring>
    using namespace std;
    
    const int MAX=10001;
    
    int Stop;//栈中的元素个数
    int cnt;//记录连通分量的个数
    int visitNum;//记录遍历的步数
    int DFN[MAX]; //记录节点u第一次被访问时的步数
    int LOW[MAX]; //记录与节点u和u的子树节点中最早的步数
    bool instack[MAX];//记录节点u是否在栈中
    int Stap[MAX];//栈
    int Belong[MAX];//记录每个节点属于的强连通分量编号
    
    int N;//节点个数
    
    vector<int> tree[MAX];
    
    void tarjan(int i)
    {
    	int j;
    	DFN[i]=LOW[i]=++visitNum;
    	instack[i]=true;
    	Stap[++Stop]=i;//将当前节点压入栈中
    	for (unsigned k=0;k<tree[i].size();k++)
    	{
    		j=tree[i][k];
    		if (!DFN[j]) //j还没有被访问过
    		{
    			tarjan(j);
    			//父节点是子节点的子节点
    			if (LOW[j]<LOW[i])
    				LOW[i]=LOW[j];
    		}
    		//与j相连,但是j已经被访问过,且还在栈中
    		//用子树节点更新节点第一次出现的时间
    		else if (instack[j] && DFN[j]<LOW[i])
    			LOW[i]=DFN[j];
    	}
    	//节点i是强连通分量的根
    	if (DFN[i]==LOW[i])
    	{
    		cnt++;
    		//输出找到的强连通分量
    		/*cout<<"连通分量"<<cnt<<": ";
    		//退栈,直至找到根为止
    		do
    		{
    			j=Stap[Stop--];
    			instack[j]=false;
    			cout<<j<<" ";
    			Belong[j]=cnt;
    		}
    		while (j!=i);
    		cout<<endl;*/
    	}
    }
    void solve()
    {
    	Stop=cnt=visitNum=0;
    	memset(DFN,0,sizeof(DFN));
    	for (int i=1;i<=N;i++)
    		if (!DFN[i])//有可能图不是连通图
    			tarjan(i);
    }
    
    int main()
    {
        int m,i,a,b;
        while(cin>>N>>m,N+m)
        {
            for(i=1;i<=N;i++)
            {
                tree[i].clear();
            }
            while(m--)
            {
                cin>>a>>b;
                tree[a].push_back(b);
            }
            solve();
            /*for(int i=1;i<=N;i++)
                cout<<Belong[i]<<" ";
            cout<<endl;*/
            if(cnt==1)
            {
                cout<<"Yes"<<endl;
            }
            else
            {
                cout<<"No"<<endl;
            }
        }
        return 0;
    }

[HDU 2006-4 Programming Contest]: http://acm.hdu.edu.cn/search.php?field=problem&key=HDU+2006-4+Programming+Contest+&source=1&searchmode=source