UVA 315 Network （割點）

題意：給出一張無向圖，求割點有多少個。

題解：割點

割點：無向連通圖中，如果删除某點後，圖的連通分量增多，則稱該點為割點。

kuangbin模闆，實作細節見代碼注釋，把橋也放進去了。

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<queue>
#include<stack>
#include<cmath>
#include<vector>
#include<fstream>
#include<set>
#include<map>
#include<sstream>
#include<iomanip>
#define ll long long
using namespace std;

/*
 * 求無向圖的割點和橋
 * 可以找出割點和橋，求删掉每個點後增加的連通塊。
 * 需要注意重邊的處理，可以先用矩陣存，再轉鄰接表，或者進行判重
 */
const int MAXN = 10010;
const int MAXM = 100010;
struct Edge {
    int to, next;
    bool cut;//是否為橋的标記
}edge[MAXM];
int head[MAXN], tot;
int Low[MAXN], DFN[MAXN], Stack[MAXN];
int Index, top;
bool Instack[MAXN];
bool cut[MAXN];
int add_block[MAXN];//删除一個點後增加的連通塊
int bridge;
void addedge(int u, int v) {
    edge[tot].to = v; edge[tot].next = head[u]; edge[tot].cut = false;
    head[u] = tot++;
}
void Tarjan(int u, int pre) {
    int v;
    Low[u] = DFN[u] = ++Index;
    Stack[top++] = u;
    Instack[u] = true;
    int son = 0;
    int pre_cnt = 0; //處理重邊，如果不需要可以去掉
    for (int i = head[u]; ~i; i = edge[i].next) {
        v = edge[i].to;
        if (v == pre && pre_cnt == 0) { pre_cnt++; continue; }
        if (!DFN[v]) {
            son++;
            Tarjan(v, u);
            if (Low[u] > Low[v])Low[u] = Low[v];
            //橋
            //一條無向邊 (u,v) 是橋，當且僅當 (u,v) 為樹枝邊，且滿足DFS(u) < Low(v)。
                if (Low[v] > DFN[u]) {
                    bridge++;
                    edge[i].cut = true;
                    edge[i ^ 1].cut = true;
                }
            //割點
            //一個頂點 u 是割點，當且僅當滿足 (1) 或 (2)
            // (1) u 為樹根，且u 有多于一個子樹。
            // (2) u 不為樹根，且滿足存在 (u,v) 為樹枝邊 (或稱父子邊，
            //    即 u 為 v 在搜尋樹中的父親)，使得 DFS(u)<=Low(v)
            if (u != pre && Low[v] >= DFN[u]) { //不是樹根
                cut[u] = true;
                add_block[u]++;
            }
        }
        else if (Low[u] > DFN[v])
            Low[u] = DFN[v];
    }
    //樹根，分支數大于 1
    if (u == pre && son > 1) cut[u] = true;
    if (u == pre) add_block[u] = son - 1;
    Instack[u] = false;
    top--;
}
void solve(int N) {
    memset(DFN, 0, sizeof(DFN));
    memset(Instack, false, sizeof(Instack));
    memset(add_block, 0, sizeof(add_block));
    memset(cut, false, sizeof(cut));
    Index = top = 0;
    bridge = 0;
    for (int i = 1; i <= N; i++)
        if (!DFN[i]) Tarjan(i, i);
}
void init() {
    tot = 0;
    memset(head, -1, sizeof(head));
}
int n, u, v;
int main() {
	while (scanf("%d", &n) && n) {
		init();
		while (scanf("%d", &u) && u) {
			while (getchar() != '\n') {
				scanf("%d", &v);
                addedge(u, v);
                addedge(v, u);
			}
		}
		solve(n);
		int ans = 0;
		for (int i = 1; i <= n; i++) {
			if (cut[i]) ans++;
		}
        printf("%d\n", ans);
	}
	return 0;
}