[ZJ][scc強連通元件][Tarjan算法] b201. F. 國家＠Morris' Blog

2012-08-28 09:40:15| 人氣1,002| 回應0 | 上一篇 | 下一篇

[ZJ][scc強連通元件][Tarjan算法] b201. F. 國家

推薦 0 收藏 0 轉貼0 訂閱站台

內容：

傳說在遙遠的古代，整個地球的大陸是一整塊，整塊大陸上有n 個城市。這些城市間有共有m 條道路相連接，不過有趣的是這些道路只能夠單向通行。有一天上帝決定把整塊大陸切成幾塊形成各自的國家。分割的策略就是把原本就可以互相聯絡的幾個城市當成一個國家（如果有一條路徑從城市i 到城市j 且有一條路徑從城市j 到城市i，則城市i 和城市j 就在同一個國家）。上帝想請你幫一個忙，他想知道每個國家的大小。也就是每個國家到底包含了幾個城市。
以下是一個簡單的例子：
如果有一條單行道從城市 i 接到城市j 用(i,j)表示如果一開始有 3 個城市，然後有3 條單行道(1, 2), (2, 1), (2, 3) 則可以分成兩個國家，分別包含了2 個城市(1, 2)和1 個城市(3)。

輸入說明：

輸入檔中會有多筆資料，每一組資料的第一行第一行包含了城市數量 n(1<=n<=100000)和單行道的數量m(1<=m<=2100000)，接下來m 行，每一行中都包含兩個數字i, j 代表有一條單行道從城市i 連到城市j(注意兩個城市間可能有不只兩條的單行道)。

輸出說明：

對於每一組資料輸出一行，內容是排序過後每個國家的大小。

範例輸入：

範例輸出：

1 2
2

提示：

出處：

2008 NPSC 高中組初賽

#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 group[maxN], gIdx;
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]) {
        int cnt = 0;
        do {
            cnt++;
            lead[stk[stkIdx]] = nd;
            in_stk[stk[stkIdx]] = 0;
        } while(stk[stkIdx--] != nd);
        group[++gIdx] = cnt;
    }
    return mn;
}
int main() {
    int n, m, x, y;
    int i;
    while(scanf("%d %d", &n, &m) == 2) {
        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);
        }
        gIdx = -1;
        for(i = 1; i <= n; i++) {
            if(!visited[i]) {
                findIdx = 0, stkIdx = -1;
                scc(i);
            }
        }
        sort(group, group+gIdx+1);
        printf("%d", group[0]);
        for(i = 1; i <= gIdx; i++)
            printf(" %d", group[i]);
        puts("");
    }
    return 0;
}

我要檢舉

#b201#F. 國家#NPSC#Tarjan#SCC

台長： Morris

您可能對以下文章有興趣

d907. 3. 城市走法計數

d780. NOIP2009 4.靶形数独

b113. 6. 線性系統求解

[ZJ][dp] b220. 5. 蛋糕師傅的煩惱

人氣(1,002) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:[ITSA] 16th 總解答
此分類上一篇:[ZJ][歸併樹] a331. K-th Number

回應(0)