题目描述

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

思路

用tarjian求强连通分量，输出入度为0的个数即可

#include 
#include 
#include 
#include 
using namespace std;
#define maxn 600000
#define fill(x, y) memset(x, y, sizeof(x))
struct edge
{
    int from, to, next;
}e[maxn];
int ls[maxn], f[maxn], n, m, dfn[maxn], low[maxn], bcnt = 0, instack[maxn], dindex = 0, belong[maxn], in[maxn];
stack s;
void tarjan(int now)
{
    dindex++;
    dfn[now] = dindex;
    low[now] = dindex;
    s.push(now);
    instack[now] = 1;
    for (int i = ls[now]; i; i = e[i].next)
    {
        if (dfn[e[i].to] == 0)
        {
            tarjan(e[i].to);
            if (low[now] > low[e[i].to]) low[now] = low[e[i].to];
        }
        else
        {
            if (instack[e[i].to] && dfn[e[i].to] < low[now])
                low[now] = dfn[e[i].to];
        }
    }
    if (dfn[now] == low[now])
    {
        bcnt++;
        int j;
        do
        {
            j = s.top();
            s.pop();
            instack[j] = 0;
            belong[j] = bcnt;
        }
        while(now != j);
    }
}
void work()
{
    for (int i = 1; i <= n; i++)
        if (dfn[i] == 0) tarjan(i);
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        e[i] = (edge) {x, y, ls[x]};
        ls[x] = i;
    }
    work();
    for (int i = 1; i <= m; i++)
        if (belong[e[i].from] != belong[e[i].to])
            in[belong[e[i].to]]++;
    int ans = 0;
    for (int i = 1; i <= bcnt; i++)
        if (in[i] == 0) ans++;
    printf("%d\n", ans);
}