Morris' Blog

2012-08-28 09:42:47Morris

[ZJ][scc強連通元件][Tarjan算法] d197. 11504 - Dominos

留言 1 收藏 0 推薦 0

內容：

骨牌很好玩。孩子們喜歡把它們立起來排成一長排，當一張骨牌倒下，它會把下一張推倒，這一張又會把下一張推倒，一直下去。不過有時候會有某一張骨牌倒下時並沒有推倒下一張，這時候就得用手把它推倒，好使其餘的骨牌繼續倒下。

給你一些骨牌的排列方式，你的任務是要算出至少要用手推倒幾張骨牌才能讓所有的骨牌全倒下。

輸入說明：

輸入的第一行有一個整數代表以下有幾組測試資料。每組測試資料的第一行有兩個不大於 100 000 的整數：第一個整數 n 代表有幾張骨牌，骨牌的編號為 1 到 n；第二個整數 m 代表以下有幾行測資，每行有兩個整數 x 和 y，表示如果 x 骨牌倒下時，y 骨牌也會跟著倒下。

輸出說明：

對於每組測試資料，輸出含有一個整數的一行。該整數表示至少要用手推倒幾張骨牌才能讓所有的骨牌全倒下。

範例輸入：

範例輸出：

提示：

UVa 原題

上傳 UVa 時需用 scanf, printf 才不會超時。

出處：

UVa ACM 11504 (管理：snail)

這題比較複雜, 先把強連通元件縮成一個點, 對於新的圖, 找出 indeg 為 0 的個數。

PS. ZJ 過得了, 但是 UVa Online Judge 過不了, 死活的 RE

#include <stdio.h>
#include <vector>
#include <stack>
#include <algorithm>
#define maxN 100010
using namespace std;
vector<int> g[maxN];
int stk[maxN], stkIdx;
int visited[maxN], in_stk[maxN];
int vfind[maxN], findIdx;
int lead[maxN];
int scc(int nd) {
    visited[nd] = in_stk[nd] = 1;
    stk[++stkIdx] = nd;
    vfind[nd] = ++findIdx;
    int mn = vfind[nd];
    for(vector<int>::iterator it = g[nd].begin();
        it != g[nd].end(); it++) {
        if(!visited[*it]) {
            mn = min(mn, scc(*it));
        }
        if(in_stk[*it]) {
            mn = min(mn, vfind[*it]);
        }
    }
    if(mn == vfind[nd]) {
        do {
            lead[stk[stkIdx]] = nd;
            in_stk[stk[stkIdx]] = 0;
        } while(stk[stkIdx--] != nd);
    }
    return mn;
}
int main() {
    int n, m, t, x, y;
    int i;
    scanf("%d", &t);
    while(t--) {
        scanf("%d %d", &n, &m);
        for(i = 1; i <= n; i++) {
            g[i].clear();
            vfind[i] = visited[i] = in_stk[i] = 0;
            lead[i] = i;
        }
        while(m--) {
            scanf("%d %d", &x, &y);
            g[x].push_back(y);
        }
        for(i = 1; i <= n; i++) {
            if(!visited[i]) {
                findIdx = 0, stkIdx = -1;
                scc(i);
            }
        }
        int indeg[100005] = {};
        for(i = 1; i <= n; i++) {
            for(vector<int>::iterator it = g[i].begin();
                it != g[i].end(); it++) {
                if(lead[*it] != *it)
                    indeg[*it]++;
                if(lead[i] != lead[*it])
                    indeg[lead[*it]]++;
            }
        }
        int ans = 0;
        for(i = 1; i <= n; i++)
            if(!indeg[i] && lead[i] == i)
                ans++;
        printf("%d\n", ans);
    }
    return 0;
}

上一篇：[ZJ] a264. 骰子疊疊樂

下一篇：[ZJ][二分Greedy] d830. 暗門2