[JOI合宿]2009-Day2:Advertisement

ローカルでAC済み.
強連結成分分解の練習問題として良い問題です.

強連結成分分解をして, 同じ強連結成分を１つのグループと見ます.
このグループで, 辺を逆にしたグラフを構築して, 他のグラフへの辺が存在しないグループに情報を与えると, 全てのグループへ情報を与えられます.

無駄に(?) setを使っているので, O((m+n)log(m+n))くらいで、十分早く動きます.
[訂正] setなんて使わなくても大丈夫でした (O(m+n))

#include <cstdio>
#include <vector>
#include <algorithm>

#define MAX_N (100000)

using namespace std;


int N;
vector<int> G[MAX_N];
vector<int> rG[MAX_N];
vector<int> compress[MAX_N];
vector<int> vs;
bool used[MAX_N];
bool group[MAX_N];
int cmp[MAX_N];

void addEdge(int from, int to)
{
    G[from].push_back(to);
    rG[to].push_back(from);
}

void dfs(int v)
{
    used[v] = true;
    for (int i = 0; i < G[v].size(); i++){
        if (!used[G[v][i]]){
            dfs(G[v][i]);
        }
    }
    vs.push_back(v);
}

void revDfs(int v, int k)
{
    used[v] = true;
    cmp[v] = k;
    for (int i = 0; i < rG[v].size(); i++){
        if (!used[rG[v][i]]){
            revDfs(rG[v][i], k);
        }
    }
}

int scc()
{
    int ret;
    memset(used, 0, sizeof(used));
    vs.clear();
    
    for (int i = 0; i < N; i++){
        if (!used[i]){
            dfs(i);
        }
    }
    
    memset(used, 0, sizeof(used));
    
    ret = 0;
    for (int i = vs.size() - 1; i >= 0; i--){
        if (!used[vs[i]]){
            revDfs(vs[i], ret++);
        }
    }
    
    for (int i = 0; i < N; i++){
        for (int j = 0; j < G[i].size(); j++){
            if (cmp[i] != cmp[G[i][j]]){
                compress[cmp[G[i][j]]].push_back(cmp[i]);
            }
        }
    }
    
    return (ret);
}

int main()
{
    int M;
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < M; i++){
        int p, q;
        scanf("%d %d", &p, &q);
        addEdge(--p, --q);
    }
    
    int k = scc();
    
    int ans = 0;
    memset(used, 0, sizeof(used));
    
    for (int i = 0; i < k; i++){
        if (compress[i].size() == 0){
            ans++;
        }
    }
    
    printf("%d\n", ans);
    
    return (0);
}