网络

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1876 字
若干组数据，每组第一行为地点数N，随后若干行
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1522
// 题意：若干组数据，每组第一行为地点数 N，随后若干行每行给出一个地点及与它直连的地点，单独一个 0 结束该组，N = 0 结束输入；统计每组中「去掉后图会变得不连通」的地点个数。
// 思路：把整组读成无向图后跑 Tarjan 求割点：非根结点 u 只要有儿子 v 满足 low[v] >= dfn[u] 就是割点，DFS 树的根要有两个及以上儿子才是割点。
// 1. 每行是「一个点 + 它的若干邻居」，要按行读取而不是按数字流读取，否则分不清哪里换行。
// 2. 图可能不连通，要对每个未访问的点都作为根跑一次 Tarjan。
// 复杂度：O(N + M) 时间 / O(N + M) 空间
// 易错点：行内第一个数字是要描述的点，剩下的才是邻居，别把邻居当成新的行首点。
// 易错点：根结点的判定与其余结点不同，必须单独按儿子个数是否大于一来判断，否则会把链首误判成割点。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
vector<int> g[MAXN];
int dfn[MAXN], low[MAXN], idx;
bool iscut[MAXN];
void tarjan(int u, int root){
    dfn[u] = low[u] = ++idx;
    int child = 0;
    for(int k = 0; k < (int)g[u].size(); k++){
        int v = g[u][k];
        if(!dfn[v]){
            child++;
            tarjan(v, root);
            low[u] = min(low[u], low[v]);
            if(u != root && low[v] >= dfn[u]) iscut[u] = true;
        }else{
            low[u] = min(low[u], dfn[v]);
        }
    }
    if(u == root && child > 1) iscut[root] = true;
}
int main(){
    int N;
    while(cin >> N){
        if(N == 0) break;
        string line;
        getline(cin, line);
        for(int i = 0; i <= N; i++){
            g[i].clear();
            dfn[i] = 0;
            low[i] = 0;
            iscut[i] = false;
        }
        while(true){
            if(!getline(cin, line)) return 0;
            stringstream ss(line);
            int u;
            if(!(ss >> u)) continue;
            if(u == 0) break;
            int v;
            while(ss >> v){
                g[u].push_back(v);
                g[v].push_back(u);
            }
        }
        idx = 0;
        for(int i = 1; i <= N; i++){
            if(!dfn[i]) tarjan(i, i);
        }
        int ans = 0;
        for(int i = 1; i <= N; i++){
            if(iscut[i]) ans++;
        }
        cout << ans << "\n";
    }
    return 0;
}
网络

正文

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