TCO '09 Final Easy FractalWheels

問題

方針

まず、hとdを決めると、頂点数と辺の数が定まるので、
グラフの頂点数と辺数からh,dの候補を絞り込む。

h,dが決まると、wheelの「中心」が決まる。
中心からグラフがFractal Wheelかどうかを判定していく。

あるノードに注目すると、まずそのノードが正しい数の子ノードを持っていなくてはならない。
更にその子ノードがきちんと輪を描いているかを見る。

これを再帰的に繰り返してグラフをチェックする。

ソースコード

よくこんなスパゲッティが通るな。。。

int N; bool visit[1000],target[1000];
vector<vi> g;


bool dfs(vi &v,int c,int p,int s,int pt){
	
	//cerr<<"dfs c:"<<c<<" p;"<<p<<" s:"<<s<<" pt;"<<pt<<endl;
	
	int cnt=0;
	rep(i,g[c].size())if(g[c][i]!=p&&target[g[c][i]])cnt++;
	if(p==-1&&cnt!=2||p!=-1&&cnt!=1)return 0;
	
	if(c==s){
		if(pt==v.size())return 1;
		if(pt!=0)return 0;
	}
	
	rep(i,g[c].size())if(g[c][i]!=p&&target[g[c][i]])return dfs(v,g[c][i],c,s,pt+1);
}

bool cycle(vi &v){
	rep(i,N)target[i]=0; rep(i,v.size())target[v[i]]=1;
	return dfs(v,v[0],-1,v[0],0);
}

bool rec(int c,int p,int h,int d,int l){
	
	//cerr<<"c: "<<c<<" p: "<<p<<" h: "<<h<<" d: "<<d<<" l: "<<l<<endl;
	//dbg(g[c].size());
	
	if(l==d+1){
		if(g[c].size()!=3)return 0;
		return 1;
	}
	if(l==0&&g[c].size()!=h)return 0;
	if(0<l&&l<=d&&g[c].size()!=h+3)return 0;
	
	vi v;
	rep(i,g[c].size())if(g[c][i]!=p&&!visit[g[c][i]])v.pb(g[c][i]), visit[g[c][i]]=1;
	//rep(i,v.size())cerr<<v[i]<<(i==v.size()-1?"\n":" ");
	
	if(v.size()!=h||!cycle(v))return 0;
	rep(i,v.size())if(!rec(v[i],c,h,d,l+1))return 0;
	return 1;
}

bool ok(int h,int d){
	
	rep(i,N)if(g[i].size()==h){
		rep(j,N)visit[j]=0; visit[i]=1;
		if(rec(i,-1,h,d,0))return 1;
	}
	return 0;
}

class FractalWheels {
	public:
	vector <int> describeWheel(int N, vector <string> edges) 
	{
		int E=0;
		::N=N;
		g=vector<vi>(N);
		
		string s=accumulate(all(edges),string());
		rep(i,s.size())if(s[i]==',')s[i]=' ';
		stringstream ss(s);
		int a,b;
		while(ss>>a>>b){
			g[a].pb(b); g[b].pb(a); E++;
		}
		
		//dbg(N); dbg(E);
		
		for(int h=3;h<=N-1;h++){
			int n=h+1, e=2*h;
			for(int d=0;;d++){
				
				if(n==N&&e==E && ok(h,d)){
					vi ans;
					ans.pb(d); ans.pb(h);
					return ans;
				}
				
				n=n*h+1; e=e*h+2*h;
				if(n>N||e>E)break;
			}
		}
		
		return vi();
	}
};