HDU1269 - 迷宫城堡(强连通)

题目链接：

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

---

题目大意：

给出一个有向图，判断是否为一个强连通的图。

---

解题过程：

看完了lrj的白书后去刷的题，裸的板子题，当tarjan练手。

---

题目分析：

对原图进行强连通分量分解，判断强连通分量的数量是否为1。

---

AC代码：

#include <bits/stdc++.h>
using namespace std;

int n, m;

const int MAX = 10000+10;

vector<int> edge[MAX];

//pre表示访问的时间，low是当前节点及其儿子节点能回到的最早的祖先，mark是所在强连通分量的编号
//剩下两个变量是用来计数
int pre[MAX], low[MAX], mark[MAX], dfs_clock, scc_cnt;
stack<int> S;

void dfs(int u) {
    pre[u] = low[u] = ++dfs_clock;
    S.push(u);
    for (int i = 0; i < edge[u].size(); i++) {
        int v = edge[u][i];
        if (!pre[v]) {
            dfs(v);
            //用当前节点的儿子节点更新low数组
            low[u] = min(low[u], low[v]);
        }
        else if (!mark[v]) {
            //用当前节点能回到的祖先节点更新low数组
            low[u] = min(low[u], pre[v]);
        }
    }
    //如果当前节点及其儿子节点都不能返回到更早的祖先节点，那么当前节点就是一个强连通分量的第一次访问到的节点
    if (low[u] == pre[u]) {
        scc_cnt++;
        int x;
        //将当前节点的儿子节点出栈
        do {
            x = S.top(); S.pop();
            mark[x] = scc_cnt;
        } while (x != u);
    }
}

void find_scc(int n) {
    dfs_clock = scc_cnt = 0;
    memset(mark, 0, sizeof(mark));
    memset(pre, 0, sizeof(pre));
    for (int i = 1; i <= n; i++) {
        if (!pre[i]) dfs(i);
    }
}

int main() {
    while (~scanf("%d %d", &n, &m) && (n + m)) {
        for (int i = 1; i <= n; i++) edge[i].clear();
        for (int i = 0; i < m; i++) {
            int u, v;
            scanf("%d %d", &u, &v);
            edge[u].push_back(v);
        }
        find_scc(n);
        if (scc_cnt != 1) printf("No\n");
        else printf("Yes\n");
    }
}