信息传递

问题描述

有 $n$ 个人，每个人都有一个编号，从 $1$ 到 $n$ 。
如果 $A$ 得知一个消息，那么他一定会告诉 $B$ 。
问最少把消息告诉几个人，能让所有人得知这个消息。

输入格式

第一行两个整数 $n,m$ , $1\le n,m\le 10^6$，表示有 $n$ 个人
接下来 $m$ 行，每行给出一个关系形如 $A,B$ ，表示如果 $A$ 得知一个消息，那么他一定会告诉 $B$ 。

输出格式

输出一行，一个数，代表答案

样例输入

10 10
1 3
2 4
4 5
2 8
5 2
5 9
6 8
9 2
10 5
5 8

样例输出

4  

样例解释

只需要告诉 $1,6,7,10$ 四个人即可

#include <bits/stdc++.h>
using namespace std;
#define MAXN 1000005
int n, m, a, b,c[MAXN], dfn[MAXN], vis[MAXN], dcnt = 0, scnt = 0, d[MAXN];
vector<int> G1[MAXN], G2[MAXN], E[MAXN];

void dfs1(const int& x) {
    vis[x] = 1;
    for (const auto& y : G1[x])
        if (!vis[y])
            dfs1(y);
    dfn[++dcnt] = x;
}

void dfs2(const int& x) {
    c[x] = scnt;//记录该点属于哪个强连通分量
    for (const auto& y : G2[x])
        if (!c[y])
            dfs2(y);
}

void kosaraju() {
    dcnt = 0;
    scnt = 0;//强连通分量的编号
    for (int i = 1; i <= n; i++)
        if (!vis[i])
            dfs1(i);
    for (int i = n; i >= 1; i--)
        if (!c[dfn[i]]) {
            ++scnt;//强连通分量数量加1
            dfs2(dfn[i]);
        }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; ++i) {
        scanf("%d%d", &a, &b);
        G1[a].emplace_back(b);
        G2[b].emplace_back(a);//反图
    }
    kosaraju();
    for (int i = 1; i <= n; i++)
        for (const auto& j : G1[i])
            if (c[i] != c[j])//避免出现自环
                E[c[i]].push_back(c[j]);//为缩点后的新图添加从强连通分量i到j的边
    for (int i = 1; i <= scnt; i++) {
        sort(E[i].begin(), E[i].end());
        E[i].erase(unique(E[i].begin(), E[i].end()), E[i].end());//去除重复边
        for (const auto& v : E[i])
            d[v]++;//缩点后的新图的每个点（强连通分量）的入度
    }
    int cnt = 0;
    for (int i = 1; i <= scnt; i++)
        if (d[i] == 0)//统计入度为0的强连通分量的数目
            ++cnt;
    cout << cnt;//输出入度为0的强连通分量的数目
    return 0;
}