描述

传送门：hdu-1269

为了训练小希的方向感，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”。

Examples

intput
1
2
3
4
5
6
7
8
9
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
output
1
2
Yes
No

思路

Tarjan的模板题，求有向图的强连通分量。

代码

#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,n)  for(int i=a;i<n;i++)
#define repd(i,a,n)  for(int i=n-1;i>=a;i--)
#define CRL(a,x) memset(a,x,sizeof(a))
const int N=1e5+5;

int DFN[N],Low[N],Clock,Begin[N],ans;bool InStack[N];
struct node{int To,Next;};      //链式向前星存图
vector<node> Edge;
stack <int> S;

void Init(){
    CRL(DFN,0);CRL(Low,0);
    CRL(Begin,-1);CRL(InStack,false);
    while(!S.empty())S.pop();
    Edge.clear();
    ans=Clock=0;
}

void Tarjan(int u){
    S.push(u);InStack[u]=true;      //入栈
    DFN[u]=Low[u]=++Clock;          //维护DFS序
    for(int i=Begin[u];i!=-1;i=Edge[i].Next){       //遍历边
        if(!DFN[Edge[i].To]){
            Tarjan(Edge[i].To);
            Low[u]=min(Low[u],Low[Edge[i].To]);
        }
        else if(InStack[Edge[i].To])
            Low[u]=min(Low[u],DFN[Edge[i].To]);
    }
    if(DFN[u]==Low[u]){         //弹出关键点之前的点，构成强连通分支
        ans++;int tem;
        do{
            tem=S.top();
            S.pop();
            InStack[tem]=false;
        }while(tem!=u);
    }
}

int main()
{
    std::ios::sync_with_stdio(false);   //关闭流同步，加速读写
    int n,m,a,b;
    while(cin>>n>>m&&(n||m)){
        Init();
        rep(i,0,m){
            cin>>a>>b;
            Edge.push_back(node {b,Begin[a]});
            Begin[a]=Edge.size()-1;
        }

        rep(i,1,n+1)
            if(!DFN[i]) Tarjan(i);      //Tarjan

        puts(ans==1? "Yes":"No");       //联通分支数是否为1
    }
    return 0;
}