【 UVA - 315 Network】（求割点 Tarjan算法）

题意：求割点

割点概念：

在无向连通图中，如果将其中一个点以及所有连接该点的边去掉，图就不再连通，那么这个点就叫做割点（cut vertex / articulation point）。

Tarjan算法求割点

模板代码：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <map>
#include <set>
#include <bitset>
#include <cctype>
#include <cstdlib>
#include <queue>
#include <cmath>
#include <stack>
#include <ctime>
#include <string>
#include <vector>
#include <sstream>
#include <functional>
#include <algorithm>
using namespace std;

#define mem(a,n) memset(a,n,sizeof(a))
#define memc(a,b) memcpy(a,b,sizeof(b))
#define rep(i,a,n) for(int i=a;i<n;i++) ///[a,n)
#define dec(i,n,a) for(int i=n;i>=a;i--)///[n,a]
#define pb push_back
#define fi first
#define se second
#define IO ios::sync_with_stdio(false)
#define fre freopen("in.txt","r",stdin)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
typedef long long ll;
typedef unsigned long long ull;
const double PI=acos(-);
const double E=;
const double eps=;
const int INF=;
const int MOD=;
const int N=+;
const ll maxn=+;
const int dir[][]= {-,,,,,-,,};
int dfn[N];
///dfn[u]表示顶点u第几个被（首次）访问，
int low[N];
///low[u]表示顶点u及其子树中的点，通过非父子边（回边），能够回溯到的最早的点（dfn最小）的dfn值（但不能通过连接u与其父节点的边）
bool cut[N];///记录割点
int par[N];///记录父节点
vector<int>g[N];
int n;
bool vis[N];
void init()
{
    mem(cut,);
    mem(vis,);
    mem(par,-);
    mem(dfn,);
    mem(low,);
    rep(i,,n+) g[i].clear();
}
void tarjan(int u,int fa)
{
    static int cnt=;
    int children=;
    dfn[u]=low[u]=cnt++;
    vis[u]=;
    for(int v:g[u])/// 遍历与u相邻的所有顶点
    {
        if(!vis[v])
        {
            children++;/// 递增子树数量
            tarjan(v,u);/// 继续DFS
            low[u]=min(low[u],low[v]);/// DFS完毕，low[v]已求出，如果low[v]<low[u]则更新low[u]
            if(fa == - && children >= ) /// 如果是根节点且有两棵以上的子树则是割点
                cut[u]=;
            if(fa != - && low[v] >= dfn[u]) /// 如果不是根节点且low[v]>=dfn[u]则是割点
                cut[u]=;
        }
        else if(v != fa) /// (u, v)为回边，且v不是u的父亲
            low[u]=min(low[u],dfn[v]);
    }
}
void solve()
{
    int ans=;
    tarjan(,-);
    for(int i=; i<=n; i++)
        if(cut[i]) ans++;
    printf("%d\n",ans);
}
int main()
{
    while(~scanf("%d",&n),n)
    {
        init();
        int u,v;
        while(scanf("%d",&u),u)
        {
            while(getchar()!='\n')
            {
                scanf("%d",&v);
                // printf("u=%d  v=%d\n",u,v);
                g[u].pb(v);
                g[v].pb(u);
            }
        }
        solve();
    }
    return ;
}