(UVA) 315 - Network [割點 cut vertex]

https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=251

裸割點題：用Tarjan算法 的 low 函數：不經過父節點所能到達的最上面深度！實作就看code吧！這裡不需要考慮重邊的部分，因為是cut vertex，重邊的話回到父節點，其實沒差。

#include <iostream>
#include <stdio.h>
#include <cstring>
#include <vector>
using namespace std;

const int MAX_N = 103;

int low[MAX_N];
int depth[MAX_N];
vector<int> edg[MAX_N];
bool visit[MAX_N];
int cut_vertex[MAX_N];
int son[MAX_N];

void dfs(int id,int cur_depth,int parent) {
    visit[id]=true;
    depth[id]=cur_depth;
    low[id]=cur_depth;
    for (auto i=edg[id].begin();i!=edg[id].end();i++) {
        int tmp=*i;
        if (visit[tmp]==true) {
            if (depth[tmp]<low[id] && tmp!=parent) low[id]=depth[tmp];
        }
        else {
            son[id]++;
            dfs(tmp,cur_depth+1,id);
            if (low[tmp] < low[id]) low[id]=low[tmp];
            else if (low[tmp] >= cur_depth && id!=1) cut_vertex[id]=1;
        }
    }
    if (id==1 && son[1]>1) cut_vertex[1]=1;
}

int main (){
//    freopen("output.txt","w",stdout);
    int n;
    while (scanf("%d",&n) != EOF) {
        if (!n) break;
        for (int x=0;n>=x;x++) {
            visit[x]=false;
            edg[x].clear();
            cut_vertex[x]=0;
            son[x]=0;
        }
        int p;
        while (scanf("%d",&p)) {
            if (p==0) break;
            int t;
            char c;
            while (scanf("%d%c",&t,&c)) {
                edg[t].push_back(p);
                edg[p].push_back(t);
                if (c=='\n') break;
            }
        }
        dfs(1,1,1);
        int sum=0;
        for (int x=1;n>=x;x++) {
            sum += cut_vertex[x];
        }
        printf("%d\n",sum);
    }
}