Algoogle

Algorithm for Programming Contest

JOI 春合宿 2009 Advertisement

Category: JOI Tag: strongly-connected-component

Advertisement

問題概要


誰が誰の連絡先を知っているかの情報が与えられる.
このとき, 情報を最小何人に伝えれば全員に情報が行き渡ることができるか

解法


有向グラフを考える.
基本的には自分の連絡先を誰にも知られていない人に伝える.
しかし閉路が存在するので閉路を潰してからそれを考える.
閉路を潰すには強連結成分分解してidを振りなおしてやれば良い.
あとは各強連結成分に他の成分から入ってくる辺が存在するかチェックしてやればよい.

コード


(Advertisement.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
#include <bits/stdc++.h>
using namespace std;

int n, m, f[100010], done[100010], id[100010];
vector<int> G[100010], rG[100010], vs;
vector<vector<int>> scc;

void dfs(int v) {
        if(done[v]) return;
        done[v] = 1;
        for(auto &u: G[v]) dfs(u);
        vs.push_back(v);
}

void rdfs(int v, int k) {
        if(done[v]) return;
        done[v] = 1;
        id[v] = k;
        scc.back().push_back(v);
        for(auto &u: rG[v]) rdfs(u,k);
}

int solve()
{
        for (int i = 0; i < n; i++) dfs(i);
        memset(done, 0, sizeof(done));
        reverse(begin(vs),end(vs));
        int k = 0;
        for(auto &v: vs)
                if(!done[v]) {
                        scc.push_back(vector<int>());
                        rdfs(v,k++);
                }
        for(auto &s: scc)
                for(auto &v: s){
                        if(f[id[v]]) break;
                        for(auto &u: rG[v])
                                if(id[u] != id[v]) f[id[v]] = 1;
                }

        int ans = 0;
        for (int i = 0; i < k; i++) ans += f[i]^1;
        return ans;
}

void input()
{
        cin >> n >> m;
        for (int i = 0; i < m; i++) {
                int a, b; cin >> a >> b;
                a--; b--;
                G[a].push_back(b);
                rG[b].push_back(a);
        }
}

int main()
{
        cin.tie(0);
        cin.sync_with_stdio(0);
        input();
        cout << solve() << endl;
        return 0;
}

Comments