题目

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

题解

强连通分量模板题
用来测试自己写的模板
具体思路看 强连通分量

代码

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 10005;

//Kosaraju
const int maxm = 100005;

struct Edge {
    int u,v;
    Edge():u(0),v(0) {}
    Edge(int a,int b):u(a),v(b) {}
};
int pos;
Edge edge[maxm];
list<int> L[maxn];
list<int> L2[maxn];

stack<int> s;
bool vis[maxn];
vector<int> SCC[maxn];//得到的强连通分量链表

inline void add(int u,int v) {
    edge[pos] = Edge(u,v);
    L[u].push_back(pos);
    L2[v].push_back(pos);//逆图

    pos++;
}

void DFS1(int t) {
    if(!vis[t]) {
        vis[t] = true;
        for(list<int>::iterator i = L[t].begin();i != L[t].end();i++)
            DFS1(edge[*i].v);
        s.push(t);
    }
    return;
}

void DFS2(int p,int t) {
    if(vis[t]) {
        vis[t] = false;
        SCC[p].push_back(t);
        for(list<int>::iterator i = L2[t].begin();i != L2[t].end();i++)
            DFS2(p,edge[*i].u);
    }
    return;
}

int Kosaraju(int n) {
    //第一次DFS
    for(int i = 0;i < n;i++)
        DFS1(i);

    //第二次DFS
    int p = 0;
    while(!s.empty()) {
        int t = s.top();
        s.pop();
        list< list<int> >::iterator it;
        if(vis[t])
            DFS2(p++,t);
    }
    return p;
}


int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int n,m;
    while(cin >> n >> m,!(n == 0 && m == 0)) {
        for(int i = 0;i < n;i++) {
            L[i].clear();
            L2[i].clear();
            SCC[i].clear();
            vis[i] = false;
        }
        while(!s.empty())s.pop();
        pos = 0;

        for(int i = 0;i < m;i++) {
            int a,b;
            cin >> a >> b;
            add(a - 1,b - 1);
        }

        cout << (Kosaraju(n) == 1 ? "Yes" : "No") << endl;


    }
    return 0;
}

/*
By:OhYee
Github:OhYee
Blog:http://www.oyohyee.com/
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <set>
#include <list>
#include <queue>
#include <stack>
#include <string>
#include <vector>
#include <bitset>
#include <functional>

using namespace std;

const int INF = 0x7FFFFFFF;
const double eps = 1e-10;

const int maxn = 10005;

//Tarjan
const int maxm = 100005;

struct Edge {
    int u,v;
    Edge():u(0),v(0) {}
    Edge(int a,int b):u(a),v(b) {}
};
int pos;
Edge edge[maxm];
list<int> L[maxn];

stack<int> s;
bool inStack[maxn];
vector<int> SCC[maxn];//得到的强连通分量链表
int cnt,Index;
int DFN[maxn],Low[maxn];

inline void add(int u,int v) {
    edge[pos] = Edge(u,v);
    L[u].push_back(pos);
    pos++;
}

void tarjan(int u) {
    if(DFN[u] != -1)
        return;

    DFN[u] = Low[u] = ++Index;
    s.push(u);
    inStack[u] = true;

    for(list<int>::iterator it = L[u].begin();it != L[u].end();it++) {
        int v = edge[*it].v;

        if(DFN[v] == -1) {
            tarjan(v);
            Low[u] = min(Low[u],Low[v]);
        } else if(inStack[v]) {
            Low[u] = min(Low[u],DFN[v]);
        }

    }
    if(DFN[u] == Low[u]) {
        int v = s.top();
        s.pop();
        inStack[v] = false;

        SCC[cnt++].push_back(v);

        while(u != v) {
            v = s.top();
            s.pop();
            inStack[v] = false;

            SCC[cnt - 1].push_back(v);
        }
    }
}

int Tarjan(int n) {
    cnt = 0;
    Index = 0;
    while(!s.empty())s.pop();
    memset(inStack,false,sizeof(inStack));
    memset(DFN,-1,sizeof(DFN));
    memset(Low,-1,sizeof(Low));

    for(int i = 0;i < n;i++)
        tarjan(i);
    return cnt;

}

int main() {
    cin.tie(0);
    cin.sync_with_stdio(false);

    int n,m;
    while(cin >> n >> m,!(n == 0 && m == 0)) {
        for(int i = 0;i < n;i++) {
            L[i].clear();
            SCC[i].clear();
        }
        while(!s.empty())s.pop();
        pos = 0;

        for(int i = 0;i < m;i++) {
            int a,b;
            cin >> a >> b;
            add(a - 1,b - 1);
        }

        cout << (Tarjan(n) == 1 ? "Yes" : "No") << endl;


    }
    return 0;
}