消息的传递

一本通·提高篇 · 代码 · cpp · 难度 3/5 · 共 1812 字
Tarjan缩点统计入度为零的分量
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1516
// 题意：给 N 个点的邻接矩阵，C(i, j) = 1 表示 i 能传给 j，求至少要直接告诉几个点才能让所有点都知道消息。
// 思路：Tarjan 缩点，答案为缩点 DAG 中入度为 0 的分量个数，每个这样的分量内部至少要直接通知一个人。
// 1. 矩阵里值为 1 才建边，值为 0 直接跳过，避免建出 N^2 条无用边。
// 2. N 最大 1000，数组建图即可，不需要 vector 动态扩容。
// 复杂度：O(n^2 + m) 时间 / O(n + m) 空间
// 易错点：入度统计要用缩点后的分量编号，用原图点编号会把分量内部的边也算成入度。
// 易错点：孤立点也是一个入度为 0 的分量，同样需要单独通知，不能漏掉。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
const int MAXM = 1000005;
int head[MAXN], to[MAXM], nxt[MAXM], ecnt;
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], scnt;
bool instk[MAXN];
int indeg[MAXN];
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[u] = true;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v);
            low[u] = min(low[u], low[v]);
        }
        else if(instk[v]){
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(low[u] == dfn[u]){
        scnt++;
        while(true){
            int x = stk[top--];
            instk[x] = false;
            scc[x] = scnt;
            if(x == u) break;
        }
    }
}
int main(){
    int n;
    if(!(cin >> n)) return 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++){
            int x;
            cin >> x;
            if(x == 1) add(i, j);
        }
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++){
        for(int i = head[u]; i; i = nxt[i]){
            int v = to[i];
            if(scc[u] != scc[v]) indeg[scc[v]]++;
        }
    }
    int ans = 0;
    for(int i = 1; i <= scnt; i++){
        if(!indeg[i]) ans++;
    }
    cout << ans << "\n";
    return 0;
}
消息的传递

正文

一本通·提高篇的其它内容
