杭电1269--迷宫城堡(强连通分量)

题目：http://acm.hdu.edu.cn/showproblem.php?pid=1269

 

本题题意是判断有向图中SCC 个数是否唯一， 模板题； 

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int MAXNODE = 10001;
const int MAXEDGE = 100001;

struct Edge{
    int u, v, next;
}E[MAXEDGE];

int head[MAXNODE], pre[MAXNODE], lowlink[MAXNODE], sccno[MAXNODE], Stack[MAXNODE], num[MAXNODE];
int tot, n, m, dfs_clock, top, scc_cnt;

void AddEdge(int u, int v) {
    Edge e = {u, v, head[u]};
    E[tot] = e;
    head[u] = tot++;
}

void init(){
    memset(head, -1, sizeof(head));
    tot = 0;

    int u, v;
    for (int i = 0; i < m; i++) {
        scanf("%d%d", &u, &v);
        AddEdge(u, v);
    }
}

void dfs(int u) {
    pre[u] = lowlink[u] = ++dfs_clock;
    Stack[++top] = u;

    for (int i = head[u]; i != -1; i = E[i].next) {
        int v = E[i].v;
        if (!pre[v]) {
            dfs(v);
            lowlink[u] = min(lowlink[u], lowlink[v]);
        }
        else if (!sccno[v]) lowlink[u] = min(lowlink[u], pre[v]);
    }
    int x;
    if (pre[u] == lowlink[u]) {
        scc_cnt++; //num[scc_cnt] = 0;
        while (1) {
            x = Stack[top--];
            //num[scc_cnt]++;
            sccno[x] = scc_cnt;
            if (x == u) break;
        }
    }
}

void solve() {
    memset(pre, 0, sizeof(pre));
    memset(sccno, 0, sizeof(sccno));
    dfs_clock = top = scc_cnt = 0;
    /*dfs(1);
    for(int i = 1; i <= n; i++)
    {
        if(sccno[i] != 1)
        {
            printf("No
");
            return;
        }
    }
    printf("Yes
");  */
    for(int i = 1; i <= n; i++)
        if(!pre[i])
            dfs(i);
    if(scc_cnt != 1)
        printf("No
");
    else
        printf("Yes
");
}

int main() {
    while(scanf("%d%d", &n, &m) != EOF , n+m)
    {
        init();
        solve();
    }
    return 0;
}

贴个并查集做法， 并查集有点好用。 两个并查集，一个反向处理有向边。  

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int father[3][10001];

int find(int a, int i)
{
    if(father[i][a] == a)
        return a;
    else
        return find(father[i][a], i);
}

int n, m;
void mercy(int a , int b)
{
    int P, Q; 
    if(a != n)                //Important; 
    {
        P = find(a, 0);
        Q = find(b, 0);
        if(P != Q)
            father[0][a] = b;  // Detail;
    }    
    if(b != n)
    {
        P = find(a, 1);
        Q = find(b, 1);
        if(P != Q)
            father[1][b] = a;  
    }
}

int main()
{
    while(~scanf("%d%d", &n, &m), n+m)
    {
        for(int i = 1; i <= n; i++)
            father[0][i] = father[1][i] = i;
        for(int i = 1; i <= m; i++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            mercy(a, b);    
        }
        bool flag = true;
        for(int i = 1; i <= n; i++)
        {
            if(find(i, 0) != n || find(i, 1) != n)    
            {
                flag = false;
                break; 
            }
        }
        if(flag)
            printf("Yes
"); 
        else
            printf("No
");
    } 
    return 0;
}