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;
}
上一篇: 一些工具