题解【洛谷P2002】消息扩散

题面

题解

\(Tarjan\)裸题。

\(Tarjan\)缩点后统计入度为\(0\)的强连通分量个数，输出即可。

代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <cctype>
#define gI gi
#define itn int
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)

using namespace std;

inline int gi()
{
    int f = 1, x = 0; char c = getchar();
    while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();}
    while (c >= '0' && c <= '9') {x = x * 10 + c - '0'; c = getchar();}
    return f * x;
}

int n, m, low[100003], dfn[100003], num, tot, head[700003], nxt[700003], ver[700003];
int ans, sum, sta[700003], vis[700003], cnt, Top, in[700003], sy[700003], kok;

inline void add(int u, int v)
{
    ver[++tot] = v, nxt[tot] = head[u], head[u] = tot;
}

void Tarjan(int u)
{
    low[u] = dfn[u] = ++num; vis[u] = 1; sta[++cnt] = u;
    for (int i = head[u]; i; i = nxt[i])
    {
        int v = ver[i];
        if (!dfn[v])
        {
            Tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if (vis[v]) low[u] = min(low[u], dfn[v]);
    }
    if (dfn[u] == low[u])
    {
        ++kok;
        int y = -1;
        do
        {
            y = sta[cnt];
            sy[y] = kok;
            vis[y] = 0;
            --cnt;
        } while (y != u);
    }
}

int main()
{
    //File("P2002");
    n = gi(), m = gi();
    for (int i = 1; i <= m; i+=1)
    {
        int u = gi(), v = gi();
        add(u, v);
    }
    for (int i = 1; i <= n; i+=1) if (!dfn[i]) Tarjan(i);
    for (int i = 1; i <= n; i+=1)
    {
        for (int j = head[i]; j; j = nxt[j])
        {
            int u = ver[j];
            if (sy[u] != sy[i])
            {
                ++in[sy[u]];
            }
        }
    }
    for (int i = 1; i <= kok; i+=1)
    {
        if (!in[i]) ++ans;
    }
    printf("%d\n", ans);
    return 0;

题解【洛谷P2002】消息扩散

原文：https://www.cnblogs.com/xsl19/p/11320509.html