旅游航道

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1604 字
多组数据，每组给m个星球、n条双向航道，删掉
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1524
// 题意：多组数据，每组给 m 个星球、n 条双向航道，删掉后会让图不连通的航道叫主要航道，求其主要航道的条数；输入以一行 0 结束。
// 思路：Tarjan 求无向图的所有桥：DFS 树边 (u, v) 满足 low[v] > dfn[u] 时就是桥，统计条数即为答案。
// 1. 判桥时反向边要按下标跳过（两条互为反向的加边下标异或 1），不能用「v 等于父亲」跳过，重边会被误判成桥。
// 2. 图可能不连通，要对每个没访问过的点都作为起点跑一次 Tarjan。
// 复杂度：O(m + n) 时间 / O(m + n) 空间
// 易错点：输入的两个数含义是「点数 m、边数 n」，与常见写法相反，读反了会直接数组越界或漏读数据。
// 易错点：结束标志是 0（样例里写作 0 0），读到 m 为 0 就该停止，不能再往下读边。
#include <bits/stdc++.h>
using namespace std;
const int MAXV = 30005;
const int MAXE = 60005;
int head[MAXV], to[MAXE], nxt[MAXE], ecnt = 1;
int dfn[MAXV], low[MAXV], idx;
int bridges;
void add(int u, int v){
    to[++ecnt] = v;
    nxt[ecnt] = head[u];
    head[u] = ecnt;
}
void tarjan(int u, int ine){
    dfn[u] = low[u] = ++idx;
    for(int i = head[u]; i; i = nxt[i]){
        int v = to[i];
        if(!dfn[v]){
            tarjan(v, i);
            low[u] = min(low[u], low[v]);
            if(low[v] > dfn[u]) bridges++;
        }
        else if(i != (ine ^ 1)){
            low[u] = min(low[u], dfn[v]);
        }
    }
}
int main(){
    int m, n;
    while(cin >> m){
        if(m == 0) break;
        if(!(cin >> n)) break;
        for(int i = 1; i <= m; i++){
            head[i] = 0;
            dfn[i] = 0;
            low[i] = 0;
        }
        ecnt = 1;
        for(int i = 0; i < n; i++){
            int a, b;
            cin >> a >> b;
            add(a, b);
            add(b, a);
        }
        idx = 0;
        bridges = 0;
        for(int i = 1; i <= m; i++){
            if(!dfn[i]) tarjan(i, 0);
        }
        cout << bridges << "\n";
    }
    return 0;
}
旅游航道

正文

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