消息扩散

tarjan强连通分量 T3

有 $n$ 个城市，中间有单向道路连接，消息会沿着道路扩散，现在给出 $n$ 个城市及其之间的道路，问至少需要在几个城市发布消息才能让这所有 $n$ 个城市都得到消息。

第一行两个整数 $n,m$，表示 $n$ 个城市，$m$ 条单向道路。

以下 $m$ 行，每行两个整数 $b,e$ 表示有一条从 $b$ 到 $e$ 的道路，道路可以重复或存在自环。

一行一个整数，表示至少要在几个城市中发布消息

input

5 4
1 2
2 1
2 3
5 1

output

2

样例解释

样例中在 4, 5号城市中发布消息。

数据范围

对于 20% 的数据，$n\le 200$；
对于 40% 的数据，$n\le 2000$；
对于 1100% 的数据，$1\le n\le 10^5，1\le m\le 5\times 10^5$。

思路

和最受欢迎的牛类似, 这里先tarjan缩点后, 对于所有入度为0的点就是需要发消息的点。

代码

const int N = 1e5 + 10, M = 1e6 + 10;
int h[N], ne[M], e[M], idx;
int n, m;
int dfn[N], low[N], ts;
int stk[N], top;
int scnt;
bool instk[N];
int id[N];
bool din[N];
 
void add(int h[], int a, int b)
{
    e[idx] = b, ne[idx] = h[a], h[a] = idx++;
}
 
void tarjan(int u)
{
    dfn[u] = low[u] = ++ts;
    stk[++top] = u, instk[u] = true;
    for (int i = h[u]; ~i; i = ne[i])
    {
        int j = e[i];
        if (!dfn[j])
        {
            tarjan(j);
            low[u] = min(low[u], low[j]);
        }
        else if (instk[j])
            low[u] = min(low[u], dfn[j]);
    }
    if (dfn[u] == low[u])
    {
        ++scnt;
        int y;
        do
        {
            y = stk[top--];
            instk[y] = false;
            id[y] = scnt;
        } while (y != u);
    }
}
 
int main()
{
    FasterIO;
    mem(h, -1);
    cin >> n >> m;
    while (m--)
    {
        int a, b;
        cin >> a >> b;
        add(h, a, b);
    }
    for (int i = 1; i <= n; i++)
        if (!dfn[i])
            tarjan(i);
    for (int i = 1; i <= n; i++)
        for (int j = h[i]; ~j; j = ne[j])
        {
            int k = e[j];
            int a = id[i], b = id[k];
            if (a != b)
            {
                din[b] = true;
            }
        }
    int res = 0;
    for (int i = 1; i <= scnt; i++)
        if (!din[i])
            res++;
    cout << res << endl;
    return 0;
}