【poj1144】 Network

http://poj.org/problem?id=1144 (题目链接)

题意

  求无向图的割点。

Solution

  Tarjan求割点裸题。并不知道这道题的输入是什么意思,也不知道有什么意义= =,欺负我英语不好是吗。。。

代码

// poj1144
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<cstdio>
#include<cmath>
#include<set>
#define MOD 1000000007
#define inf 2147483640
#define LL long long
#define free(a) freopen(a".in","r",stdin);freopen(a".out","w",stdout);
using namespace std;
inline LL getint() {
LL x=0,f=1;char ch=getchar();
while (ch>'9' || ch<'0') {if (ch=='-') f=-1;ch=getchar();}
while (ch>='0' && ch<='9') {x=x*10+ch-'0';ch=getchar();}
return x*f;
} const int maxn=200;
struct edge {int to,next;}e[maxn<<2];
int head[maxn],p[maxn],dfn[maxn],low[maxn],f[maxn];
int cnt,root,n,ind; void link(int u,int v) {
e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt;
}
void Tarjan(int u,int fa) {
dfn[u]=low[u]=++ind;
f[u]=1;
for (int i=head[u];i;i=e[i].next) if (e[i].to!=fa) {
if (!f[e[i].to]) {
Tarjan(e[i].to,u);
low[u]=min(low[u],low[e[i].to]);
if (low[e[i].to]>=dfn[u] && u!=1) p[u]++;
else if (u==1) root++;
}
else low[u]=min(low[u],dfn[e[i].to]);
}
}
int main() {
while (scanf("%d",&n)!=EOF && n) {
for (int i=1;i<=n;i++) head[i]=low[i]=dfn[i]=f[i]=p[i]=0;
int u,v;cnt=root=ind=0;
while (scanf("%d",&u)!=EOF && u)
while (getchar()!='\n') {
scanf("%d",&v);
link(u,v);
}
Tarjan(1,0);
int ans=0;
if (root>1) ans++;
for (int i=2;i<=n;i++) if (p[i]) ans++;
printf("%d\n",ans);
}
return 0;
}

  

上一篇:.NET CORE——Console中使用依赖注入


下一篇:微信小程序开发模板消息的时候 出现 errcode: 41028, errmsg: "invalid form id hint: