POJ 1523 SPF (无向图割点)

<题目链接>

题目大意:

给你一个连通的无向图,问你其中割点的编号,并且输出删除该割点后,原图会被分成几个连通分量。

解题分析:

Tarjan求割点模板题。

 #include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std; #define rep(i,s,t) for(int i=s;i<=t;i++)
#define clr(i,a) memset(i,a,sizeof(i))
const int N = ;
int head[N], cnt, rt, add_block[N], dfn[N], low[N], fa[N], tot;
struct Edge{
int to, next;
}e[N*N];
inline int read(){
int r=, f=; char c=getchar();
for(; c<''||c>''; c=getchar()) if(c=='-')f=-;
for(; c>=''&&c<=''; c=getchar()) r=r*+c-'';
return f*r;
}
void add(int u, int v) {
e[++cnt].next=head[u]; head[u]=cnt; e[cnt].to=v;
e[++cnt].next=head[v]; head[v]=cnt; e[cnt].to=u;
}
void tarjan(int u, int fa) {
dfn[u]=low[u]=++tot;
int child=;
for(int i=head[u];~i; i=e[i].next) {
int v=e[i].to;
if(!dfn[v]) {
tarjan(v, u);
++child;
if(low[v]>=dfn[u])++add_block[u]; //add_block代表删除u后能够增加的分量个数
low[u]=min(low[v], low[u]);
}
else if(dfn[v]<dfn[u] && fa!=v)low[u]=min(low[u], dfn[v]);
}
if(child== && fa==-) add_block[u]=; //如果
else if(child> && fa==-) add_block[u]=child-;
} int main() {
int u, v, ncase=;
while(true) {
u=read(); if(u==) break;
v=read();
clr(head, -); clr(add_block, ); cnt=tot=; clr(dfn, ); clr(low, );
add(u, v);rt=max(rt, v);
while() {
u=read(); if(u==) break;
v=read();
add(u, v); rt=max(rt, v); //rt用来记录序号最大的节点
}
rep(i, , rt) if(head[i]!=- && !dfn[i]) tarjan(i, -);
int flag=;
printf("Network #%d\n", ++ncase);
rep(i, , rt) if(add_block[i])
printf(" SPF node %d leaves %d subnets\n", i, add_block[i]+), flag=;
if(!flag) puts(" No SPF nodes");
puts("");
}
return ;
}

2018-12-02

上一篇:ruby gem源更换国内源gems.ruby-china.org数据源


下一篇:2010 A B 2011 A B