PCK 2011 本選 - 魔方陣

問題 : 魔方陣

解法 :

無向グラフ$G$ が直線グラフであるかを判定する問題.
各頂点の次数が$2$ 以下で, 大きさ$3$ 以上のサイクルを含まなければよいが, これはUnion-Find 木で効率的にチェックすることが可能である.
0 WA で早く実装できたので良い.

コード :

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <set>

using namespace std;

int par[100000];
void init(int n)
{
	for (int i = 0; i < n; 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;
	if (rand() & 1) par[y] = x;
	else par[x] = y;
}

int main()
{
	int n, m;
	
	while (scanf("%d %d", &n, &m) && n){
		int deg[100000] = {0};
		set<pair<int, int> > used;
		init(n);
		
		bool ok = true;
		for (int i = 0; i < m; i++){
			int a, b;
			scanf("%d %d", &a, &b);
			--a; --b;
			deg[a]++;
			deg[b]++;
			if (deg[a] > 2 || deg[b] > 2) ok = false;
			if (used.find(make_pair(a, b)) != used.end()) ok = false;
			if (same(a, b)) ok = false;
			used.insert(make_pair(a, b));
			used.insert(make_pair(b, a));
			merge(a, b);
		}
		printf("%s\n", ok ? "yes" : "no");
	}	
}