1523 SPF

問題概要

連結な無向グラフで表されるコンピュータネットワークがある。
このネットワークから、1台のコンピュータを取り除いたとき、ネットワークが2つ以上のサブネットワークに分断されるとき、そのようなノードをSPFと呼ぶ。

ネットワークの全てのSPFおよび、そのノードを取り除いたときにできるサブネットワークの数を求めよ。

解法

グラフの関節点を求める問題である。
グラフの関節点は以下のようなアルゴリズムで求められる。

配列num,lowを用意する。

• 一点からdfsし、
• 行きがけに頂点に番号を小さい順に振る
• 帰りがけに、low[v]=min{num[v],num[vから出ている後退辺の行き先],low[vの子]}

を計算する。

low[]はdfsしたときの探索木を、後退辺を一度だけ通って行ける最も小さい番号の頂点である。
そして、根については（探索木において）2個以上の個があったときに関節点、
それ以外の頂点vについては、vの子wで、low[w]≧num[v]を満たすものが存在すれば関節点である。

ここで、low[w]の値の集合のうち、num[v]以上のものの個数m個とすれば、
m+1個が関節点を取り除いたときにできるサブグラフの個数となる。

ソースコード

int n,num[1000],low[1000],na,pa[1000];
pi ans[1000];
vector<vi> e;

void rec(int c,int p)
{
	num[c]=n++; pa[c]=p;
	fr(i,e[c])if(num[*i]<0)rec(*i,c);
	
	low[c]=num[c];
	fr(i,e[c])if(*i!=p)
	{
		if(num[*i]<num[c])low[c]=min(low[c],num[*i]);
		else low[c]=min(low[c],low[*i]);
	}
	
	set<int> s;
	if(c!=0)
	{
		fr(i,e[c])if(*i!=p&&low[*i]>=num[c])s.insert(low[*i]);
		if(s.empty())return;
		ans[na++]=mp(c+1,s.size()+1);
	}
	else
	{
		int cnt=0;
		fr(i,e[c])if(pa[*i]==0)cnt++;
		if(cnt>1)ans[na++]=mp(c+1,cnt);
	}
}

int main()
{
	int a,b,cs=0;
	while(scanf("%d",&a),a)
	{
		e.clear(); e.resize(1000);
		
		scanf("%d",&b); a--; b--;
		e[a].pb(b); e[b].pb(a);
		while(scanf("%d",&a),a)
		{
			scanf("%d",&b); a--; b--;
			e[a].pb(b); e[b].pb(a);
		}
		
		rep(i,1000)num[i]=-1; n=na=0;
		rec(0,-1);
		
		printf("Network #%d\n",++cs);
		if(na==0)puts("  No SPF nodes");
		else 
		{
			sort(ans,ans+na);
			rep(i,na)printf("  SPF node %d leaves %d subnets\n",ans[i].first,ans[i].second);
		}
		puts("");
	}
	return 0;
}