JOI春合宿 2011-day2 shiritori

問題文 : しりとり

解法 :
各辺を1 度だけ通るような探索をしてしまうと, 辺の数が多すぎるためうまく探索ができない.
そこで, 00 ~ 99を頂点としたグラフを考え, その間に辺を貼ることを考える.このグラフがオイラーグラフであればしりとりをすることが可能ということが分かる.

オイラーグラフである判定は, それぞれの頂点が連結であるかの判定, および入次数と出次数の関係を頂点毎にチェックすることで確認できる.

もしもオイラーグラフであれば, 実際に辺をたどっていく. このとき, 使った辺を除いた現在の頂点の入次数が正であれば, その頂点を含む強連結成分間にまだ辺があることに留意する.
ある辺を使い切った時, グラフの形が変化するので, そのときには強連結成分分解を再度行う.

O(V^2)の強連結成分分解をO(V^2)回行い, グラフの探索をO(VN)回行うので, 全体の計算量はO(V^4 + VN) となる.
ここで, V は頂点数 (= 100) である.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <climits>
#include <vector>
#include <algorithm>

#define top(x) ((x) / 100000000)
#define low(x) ((x) % 100)

using namespace std;

typedef long long lint;

int par[100];
void init()
{
	for (int i = 0; i < 100; i++) par[i] = i;
}

int find(int x)
{
	if (par[x] == x) return (x);
	return (par[x] = find(par[x]));
}

bool same(int x, int y)
{
	return (find(x) == find(y));
}

void merge(int x, int y)
{
	x = find(x);
	y = find(y);
	
	if (x == y) return;
	else if (rand() & 1) par[y] = x;
	else par[x] = y;
}

vector<lint> G[100][100];
int inDeg[100], outDeg[100];
int vNum[100][100], idx[100][100];
int gr[100];
bool vis[100];
vector<int> ord;
vector<int> sG[100], srG[100];

void dfs(int v)
{
	vis[v] = true;
	for (int i = 0; i < sG[v].size(); i++){
		if (!vis[sG[v][i]]) dfs(sG[v][i]);
	}
	ord.push_back(v);
}

void rdfs(int v, int idx)
{
	vis[v] = true;
	gr[v] = idx;
	for (int i = 0; i < srG[v].size(); i++){
		if (!vis[srG[v][i]]) rdfs(srG[v][i], idx);
	}
}

void doscc()
{
	memset(gr, -1, sizeof(gr));
	memset(vis, false, sizeof(vis));
	ord.clear();
	
	for (int i = 0; i < 100; i++){
		sG[i].clear(), srG[i].clear();
	}
	
	for (int i = 0; i < 100; i++){
		for (int j = 0; j < 100; j++){
			if (vNum[i][j] != idx[i][j]){
				sG[i].push_back(j); srG[j].push_back(i);
			}
		}
	}
	
	for (int i = 0; i < 100; i++){
		if (!vis[i]) dfs(i);
	}
	
	memset(vis, false, sizeof(vis));
	int k = 0;
	for (int i = 99; i >= 0; i--){
		if (!vis[ord[i]]) rdfs(ord[i], k++);
	}
}

int main()
{
	int N;
	
	scanf("%d", &N);
	
	init();
	
	for (int i = 0; i < N; i++){
		lint x;
		scanf("%lld", &x);
		outDeg[top(x)]++; inDeg[low(x)]++;
		G[top(x)][low(x)].push_back(x);
		vNum[top(x)][low(x)]++;
		merge(top(x), low(x));
	}
	
	bool ng = false;
	int candst = 0, canden = 0;
	for (int i = 0; i < 100; i++){
		if (inDeg[i] + 1 == outDeg[i]) candst++;
		if (outDeg[i] + 1 == inDeg[i]) canden++;
		if (abs(inDeg[i] - outDeg[i]) >= 2 || candst >= 2 || canden >= 2) ng = true;
		
		for (int j = 0; j < 100; j++){
			sort(G[i][j].begin(), G[i][j].end());
			if (!same(i, j) && (inDeg[i] || outDeg[i]) && (inDeg[j] || outDeg[j])){
				ng = true;
			}
		}
	}
	
	if (ng) return (!printf("impossible\n"));
	
	int e = -1;
	
	for (int i = 0; i < 100; i++){
		if (candst && inDeg[i] + 1 == outDeg[i]){
			e = i; break;
		}
		else if (!candst && outDeg[i]){
			e = i; break;
		}
	}
	
	doscc();
	
	for (int i = 0; i < N; i++){
		lint nxt = LLONG_MAX;
		for (int nexte = 0; nexte < 100; nexte++){
			if (vNum[e][nexte] != idx[e][nexte]){
				if ((inDeg[e] && gr[e] == gr[nexte]) || !inDeg[e]){
					nxt = min(nxt, G[e][nexte][idx[e][nexte]]);
				}
			}
		}
		
		printf("%010lld\n", nxt);
		
		idx[e][low(nxt)]++;
		if (vNum[e][low(nxt)] == idx[e][low(nxt)]) doscc();
		e = low(nxt);
		inDeg[e]--;
	}
	
	return (0);
}