题意:
给个无向图,问有多少个割点,对于每个割点求删除这个点之后会产生多少新的点双联通分量
题还是很果的
怎么求割点请参考tarjan无向图
关于能产生几个新的双联通分量,对于每个节点u来说,我们判断他是否是割点,即判断是否满足他的儿子v的low[v]>dfn[u]
而这个时候割掉这个点就会让双联通分量增加,所以搞一个数组记录一下这个操作的次数就行
请注意在是否是根节点的问题上特判
!!注意输出格式!!
#include<cstdio>
#include<algorithm>
#include<cstring>
#define N 5010
#define M 10100
#define Max(a,b,c) max(max(a,b),c)
using namespace std;
int head[N],n,m,ecnt=,u,v,dfn[N],low[N],indx,du[N],ans,isap[N],ap,task,sum[N];
struct edge
{
int u,v,nxt;
}e[M*];
void add(int u,int v)
{
e[ecnt].v=v;
e[ecnt].nxt=head[u];
e[ecnt].u=u;
head[u]=ecnt++;
e[ecnt].v=u;
e[ecnt].nxt=head[v];
e[ecnt].u=v;
head[v]=ecnt++;
}
void dfs(int u,int fa)
{
dfn[u]=low[u]=++indx;
int n_ch=;
for (int i=head[u];i;i=e[i].nxt)
{
int v=e[i].v;
if (!dfn[v])
{
dfs(v,i);
low[u]=min(low[u],low[v]);
if (low[v]>=dfn[u])
isap[u]=,ap++,sum[u]++;
n_ch++;
}
else
if (v!=fa)
low[u]=min(dfn[v],low[u]);
}
if (fa==- && n_ch==)
isap[u]=,ap--;
if (isap[u] && fa!=-) sum[u]++;
}
void init()
{
n=;
memset(sum,,sizeof(sum));
memset(head,,sizeof(head));
memset(dfn,,sizeof(dfn));
memset(isap,,sizeof(isap));
ecnt=;
ans=;
indx=;
ap=;
}
void solve()
{
if (n==) return;
task++;
for (int i=;i<=n;i++)
if (!dfn[i]) dfs(i,-);
printf("Network #%d\n",task);
if (ap==)
printf(" No SPF nodes\n");
for (int i=;i<=n;i++)
if (isap[i])
printf(" SPF node %d leaves %d subnets\n",i,sum[i]);
putchar('\n');
init();
}
int main()
{
// freopen("1.in","r",stdin);
while ()
{
while (scanf("%d",&u)!=EOF)
{
if (u==)
{
solve();
continue;
}
if (scanf("%d",&v)==EOF) break;
n=Max(n,u,v);
add(u,v);
// printf("%d %d\n",u,v);
}
if (n==) break;
}
return ;
}