网络协议

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

// 原题：https://oj.yecheng.tv/p/T1515
// 题意：n 所学校各有支援名单（每行以 0 结尾），求最少直接发给几所学校能让全网收到，以及至少新增几条支援关系能让全网强连通。
// 思路：Tarjan 缩点后，第一问是缩点 DAG 中入度为 0 的分量个数，第二问是入度 0 与出度 0 的分量个数的较大值。
// 1. 整个图已经是强连通时第二问为 0，需要单独判断，否则会算出 1。
// 2. 输入是每校一行名单，读到 0 结束该行。
// 复杂度：O(n + m) 时间 / O(n + m) 空间
// 易错点：整图已强连通（分量数为 1）时第二问答案是 0，公式 max(入度 0, 出度 0) 只在分量数大于 1 时成立。
// 易错点：名单行长度不定，要一直读到 0 为止，不能按固定列数读取。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], stk[MAXN], top, idx;
int scc[MAXN], scnt;
bool instk[MAXN];
int indeg[MAXN], outdeg[MAXN];
void tarjan(int u){
    dfn[u] = low[u] = ++idx;
    stk[++top] = u;
    instk[u] = true;
    for(int i = 0; i < (int)g[u].size(); i++){
        int v = g[u][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++){
        int x;
        cin >> x;
        while(x != 0){
            g[i].push_back(x);
            cin >> x;
        }
    }
    for(int i = 1; i <= n; i++){
        if(!dfn[i]) tarjan(i);
    }
    for(int u = 1; u <= n; u++){
        for(int i = 0; i < (int)g[u].size(); i++){
            int v = g[u][i];
            if(scc[u] != scc[v]){
                outdeg[scc[u]]++;
                indeg[scc[v]]++;
            }
        }
    }
    int src = 0;
    int snk = 0;
    for(int i = 1; i <= scnt; i++){
        if(!indeg[i]) src++;
        if(!outdeg[i]) snk++;
    }
    cout << src << "\n";
    if(scnt == 1) cout << 0 << "\n";
    else cout << max(src, snk) << "\n";
    return 0;
}
网络协议

正文

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