1236 Network of Schools

問題概要

有向グラフで表されるソフトウェア配布ネットワークが与えられる。
このネットワークについて以下の二つの値を求めよ。

• 全てのノードにソフトウェアを行き渡らせるために、最初にソフトウェア配布しなければならないノードの数。
• どんなノードに最初にソフトウェアを配布しても、全てのノードにソフトウェアが行き渡るようになるために、ネットワークに追加しなければならない最小の辺の数。

グラフのノード数≦100を満たす。

解法

グラフを強連結成分分解してDAGにする。
すると、最初にソフトを配布しなければならないノードの数は、このグラフの根（入次数0のノード）の数に等しい。

二番目の求める数は、DAGのノードの数が1なら0個で（コーナーケース）、
そうでないならDAGのmax(葉の数,根の数）である。

グラフの葉を全て次の根につなぎ、……としてループを作ればよいからである。

テストケース弱そうだったから嘘解法かも？

ソースコード

int main()
{
	int n,t; scanf("%d",&n);
	Graph g(n);
	rep(i,n)while(scanf("%d",&t),t)g[i].pb(Edge(i,t-1));
	
	vector<vi> scc;
	stronglyConnectedComponents(g,scc);
	
	int id[100],m=scc.size(); rep(i,m)fr(j,scc[i])id[*j]=i;
	bool e[100][100]={0};
	rep(i,m)e[i][i]=1;
	rep(i,n)fr(j,g[i])e[id[i]][id[j->dst]]=1;
	
	int leaf=0,root=0;
	rep(i,m)
	{
		int in=0,out=0;
		rep(j,m)if(i!=j)
		{
			if(e[i][j])out++;
			if(e[j][i])in++;
		}
		if(out==0)leaf++;
		if(in==0)root++;
	}
	
	printf("%d\n%d\n",root,m==1?0:max(root,leaf));
	return 0;
}