UVA 315 Network（tarjan求割点）

最新推荐文章于 2024-06-14 17:52:31 发布

ToRe.

最新推荐文章于 2024-06-14 17:52:31 发布

阅读量198

点赞数

分类专栏：割点/割边文章标签： tarjan

本文链接：https://blog.csdn.net/j2_o2/article/details/86654961

版权

割点/割边专栏收录该内容

5 篇文章

订阅专栏

题目连接

题意

求无向图割点数

思路

板子题，大概了解为什么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;
}