Tarjian求無向圖割點模闆 UVA - 315 Network

​​UVA - 315 Network​​

題目

給一個無向圖，不過輸入有點麻煩。求所有割點

分析

Tarjian 求無向圖割點模闆題。

原理：在 過程中有一個時間戳，每個點會被記錄兩次，開始和結束時。用兩個數組儲存 。

代碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const int mod = 1e4 + 1;
const int N = 1e4 + 10;

int n;
int dfs_clock, pre[N], low[N], iscut[N];    // 時間戳、開始點、結束點、割點數組
vector<int> e[N];                         // 存圖

void dfs(int u, int fa){                // 每次傳回目前節點的 low 值
    low[u] = pre[u] = ++dfs_clock;
    int son = 0;                        // 子節點數量
    for (int i = 0; i < e[u].size(); i++){
        int v = e[u][i];
        if(!pre[v]){                    // 如果沒有通路過 v，子節點數量增加
            son++;  
            dfs(v, u);
            low[u] = min(low[u], low[v]);     // 用後代更新
            if(low[v] >= pre[u])          // 如果有兒子最早傳回的祖先不超過 u
                iscut[u] = 1;
        }else if(v != fa && pre[v] < pre[u])
            low[u] = min(low[u], pre[v]);   // 用反向邊更新
    }
    if(fa < 0 && son == 1)
        iscut[u] = 0;                   // 特判根節點
}

void find_cut(){
    dfs_clock = 0;
    int cnt = 0;
    memset(pre, 0, sizeof pre);
    memset(iscut, 0, sizeof iscut);
    for(int i = 1; i <= n; i++){
        if(!pre[i])
            dfs(i, -1);
    }
    for(int i = 1; i <= n; i++){
        if(iscut[i])
            cnt++;
    }
    printf("%d\n", cnt);
}

int main()
{
    while(scanf("%d", &n) && n){
        for (int i = 1; i <= n; i++)
            e[i].clear();
        int u, v;
        char str;
        while(scanf("%d", &u) && u){
            while(scanf("%d%c", &v, &str)){
                e[u].push_back(v);
                e[v].push_back(u);
                if(str == '\n')
                    break;
            }
        }
        find_cut();
    }
    return 0;
}
/*

5
5 1 2 3 4
0
6
2 1 3
5 4 6 2
0
0
 */