Algoogle

Algorithm for Programming Contest

PKU 2186 Popular Cows

Category: PKU Tag: strongly-connected-component

Popular Cows

問題概要


牛達が人気だと思う人を挙げる.
推移律が成り立つとき, 自分以外の全ての牛から人気だと思われている牛の数を求めよ.

解法


強連結成分分解すると分解された強連結成分どうしはDAGになるのでその終端を見る.
終端はそこから辺が伸びてない強連結成分.
該当する強連結成分が複数ある場合は0.
そうでなければ終端の強連結成分の要素数が答え.

コード


(2186.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <cstdio>
#include <vector>
#include <cstring>

using namespace std;

int N, M;
vector<int> E[10010], rE[10010];
vector<vector<int> > scc;
int group[10010];
bool visited[10010];
vector<int> vs;

void dfs(int s){
    visited[s] = 1;
    for(int i = 0; i < E[s].size(); i++)
        if(!visited[E[s][i]]) dfs(E[s][i]);
    vs.push_back(s);
}

void rdfs(int s, int k){
    visited[s] = 1;
    group[s] = k;
    scc.back().push_back(s);
    for(int i = 0; i < rE[s].size(); i++)
        if(!visited[rE[s][i]]) rdfs(rE[s][i], k);
}

int main(){
    scanf("%d%d", &N, &M);
    for(int i = 0; i < M; i++){
        int a, b; scanf("%d%d", &a, &b);
        a--; b--;
        E[a].push_back(b);
        rE[b].push_back(a);
    }

    for(int i = 0; i < N; i++)
        if(!visited[i]) dfs(i);

    memset(visited, 0, sizeof(visited));
    int cnt = 0;
    for(int i = 0; i < N; i++)
        if(!visited[vs[N-i-1]]){
            scc.push_back(vector<int>());
            rdfs(vs[N-i-1], cnt++);
        }

    int ans = -1;
    for(int i = 0; i < scc.size(); i++){
        int g = group[scc[i][0]];
        bool exist = 0;
        for(int j = 0; j < scc[i].size(); j++){
            for(int k = 0; k < E[scc[i][j]].size(); k++)
                if(g != group[E[scc[i][j]][k]]) {
                    exist = 1;
                    break;
                }
            if(exist) break;
        }
        if(!exist and ans >= 0) {
            ans = 0;
            break;
        }
        if(!exist) ans = scc[i].size();
    }

    printf("%d\n", ans);
    return 0;
}

Comments