欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 315 Network(tarjan求割点)

程序员文章站 2022-05-27 16:22:25
...
题目连接
题意

求无向图割点数

思路

板子题,大概了解为什么low[u] = min(low[u], dfn[v])。
毒瘤输入

代码
#include <bits/stdc++.h>
using namespace std;

int low[105], cut[105], dfn[105], tot = 0, n, ans;
vector<int> e[105];

void tarjan(int u, int fa)
{
    dfn[u] = low[u] = ++tot;
    int son = 0;
    for(int i = 0; i < e[u].size(); ++i)
    {
        int v = e[u][i];
        if(!dfn[v])
        {
            tarjan(v,fa);
            low[u] = min(low[u], low[v]);
            if(low[v] >= dfn[u] && u != fa) cut[u] = 1;
            if(u == fa) ++son;
        }
        low[u] = min(low[u], dfn[v]);
    }
    if(u == fa && son > 1) cut[fa] = 1;
}

int main()
{
    int n, m;
    while(scanf("%d",&n),n)
    {
        for(int i = 1; i <= n; ++i) e[i].clear(), cut[i] = low[i] = dfn[i] = 0;
        ans = 0;
        int u, v;
        char c;
        while(scanf("%d",&u),u)
        {
            while(scanf("%d%c",&v,&c))
            {
                e[u].push_back(v);
                e[v].push_back(u);
                if(c=='\n') break;
            }
        }
        for(int i = 1; i <= n; ++i) if(!dfn[i]) tarjan(i,i);
        for(int i = 1; i <= n; ++i) if(cut[i]) ++ans;
        printf("%d\n",ans);
    }
    return 0;
}
相关标签: tarjan