割点数量

2024-08-14

求解无向图中的割点数量

#include <bits/stdc++.h>
#define io cin.tie(0), cout.tie(0), ios::sync_with_stdio(false)
#define LL long long
#define ULL unsigned long long
#define EPS 1e-8
#define INF 0x7fffffff
#define SUB -INF - 1
using namespace std;
const int N = 109;
int low[N], num[N], dfn;
bool iscut[N];
vector<int> G[N];
void dfs(int u, int fa)
{
    low[u] = num[u] = ++dfn;
    int child = 0;
    for (int i = 0; i < G[u].size(); i++)
    {
        int v = G[u][i];
        if (!num[v])
        {
            child++;
            dfs(v, u);
            low[u] = min(low[v], low[u]);
            if (low[v] >= num[u] && u != 1)
                iscut[u] = true;
        }
        else if (num[v] < num[u] && v != fa)
            low[u] = min(low[u], num[v]);
    }
    if (u == 1 && child >= 2)
        iscut[1] = true;
}
int main()
{
    int ans, n;
    while (~scanf("%d", &n) != -1)
    {
        if (n == 0)
            break;
        memset(low, 0, sizeof(low));
        memset(num, 0, sizeof(num));
        dfn = 0;
        for (int i = 0; i <= n; i++)
            G[i].clear();
        int a, b;
        while (scanf("%d", &a) && a)
            while (getchar() != '\n')
            {
                scanf("%d", &b);
                G[a].push_back(b);
                G[b].push_back(a);
            }
        memset(iscut, false, sizeof(iscut));
        ans = 0;
        dfs(1, 1);
        for (int i = 1; i <= n; i++)
            ans += iscut[i];
        printf("%d\n", ans);
    }
    return 0;
}