1737 Connected Graph

問題概要

頂点数nの単純無向グラフで、連結なものはいくつあるか求めよ。
n≦18とする。

解法

n≦7くらいまでは全探索できるので、全探索したの結果を数列辞典で検索（酷
表があったので埋め込みしてサブミット。

ソースコード

小さいケースをテストしたコード。

int bit(int b)
{
	int r=0;
	for(;b;b&=b-1)r++;
	return r;
}

int p[10];
int root(int x)
{
	if(x==p[x])return x;
	return p[x]=root(p[x]);
}

int solve(int c)
{
	int ret=0;
	rep(i,1<<c*(c-1)/2)
	{
		rep(j,c)p[j]=j;
		rep(j,c*(c-1)/2)if(1<<j&i)
		{
			int a,b=j;
			for(a=0;;a++)
			{
				if(b<a)break;
				b-=a;
			}
			
			a=root(a); b=root(b); if(a<b)swap(a,b);
			if(a!=b)p[a]=b;
		}
		rep(j,c)if(root(j)!=0)goto FAIL;
		ret++; FAIL:;
	}
	return ret;
}
int main()
{
	rep(n,7)cout<<solve(n+1)<<endl;
	return 0;
}