poj 1523 spf割点を求める
1735 ワード
カットポイントを求めるテンプレートの問題がありません.tarjanの運用です.
#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=1e3+9,N=1e3;
bool e[maxn][maxn];
int dfn[maxn],low[maxn],count,in[maxn];
void tarjan(int t,int from)
{
dfn[t]=low[t]=++count;
int ret=0;
for(int i=1;i<=N;i++)
if(e[t][i])
{
if(i==from) continue;
if(dfn[i]==-1)
{
ret++;
tarjan(i,t);
low[t]=min(low[t],low[i]);
if(low[i]>=dfn[t])
in[t]++;
}
else
{
low[t]=min(low[t],dfn[i]);
}
}
if(t==from)
in[t]=ret-1;
}
int main()
{
// freopen("in.txt","r",stdin);
int from,to,tcase=0;
while(scanf("%d",&from),from)
{
scanf("%d",&to);
e[from][to]=1;
e[to][from]=1;
while(scanf("%d",&from),from)
{
scanf("%d",&to);
e[from][to]=1;
e[to][from]=1;
}
// printf("hi");
count=0;
memset(dfn,-1,sizeof(dfn));
memset(in,0,sizeof(in));
for(int i=1;i<=N;i++)
if(dfn[i]==-1)
tarjan(i,i);
printf("Network #%d
",++tcase);
int cnt=0;
for(int i=1;i<=N;i++)
{
if(in[i]>0)
{
printf(" SPF node %d leaves %d subnets
",i,in[i]+1);
cnt++;
}
}
if(!cnt)
printf(" No SPF nodes
");
memset(e,0,sizeof(e));
printf("
");
}
return 0;
}