AOJ 2347 Sunny Graph

組合せ最適化で最大マッチングのところを読んで実装したので、解いた。
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2347

問題概要: グラフがある。頂点1を含む長さ3以上の奇サイクルをとり、残りの頂点で完全マッチングを作れるか判定せよ。

解法:

まずEdmondsの最大マッチングアルゴリズムを走らせる。奇サイクルは1点+完全マッチングに分解できるので、得られたマッチングのサイズが(頂点数-1)/2でなければNoを出力。

そうでない場合、このグラフのGallai-Edmonds分解を考える。Gallai-Edmonds分解とは、頂点集合を「ある完全マッチングが存在し、それに含まれない点」「その隣接点」「それ以外」の3つに分ける分割のこと。

条件より、頂点1はGallai-Edmonds分解で最初の集合に入る。Gallai-Edmonds分解において、最初の集合(に頂点を制限したグラフ)の全ての連結成分は、どの1点を除いても完全マッチングを持つという性質を持つ。そのようなグラフは全ての耳の長さが奇数の耳分解を持つので、頂点数が3以上なら奇サイクルとマッチングへの分解を持つ。

よって、Gallai-Edmonds分解において頂点1が最初の集合に入り、かつその連結成分のサイズが3以上なら、(残りの成分は2番目の集合の点とうまく結び付ければ)、条件を満たす。逆に、サイズが1なら、(その点は2番目の集合の点としか結ばれておらず、2番目の集合の点は最初の集合の点以外と(Tutte条件より)結ばれないため)、条件を満たさない。

Gallai-Edmonds分解は、単にEdmondsのアルゴリズムでの交互木の根からの距離の偶奇を求めれば求まるので、単に頂点1が(根からの距離偶数の)あるサイズ3以上の花に含まれるかを判定すればよい。

計算量は最大マッチングパート以外は微小で、O(N^3)となる。

#include<stdio.h>
#include<vector>
#include<algorithm>
using namespace std;
int match[222];
int par[222];
int root[222];
vector<int>pat[222];
int state[222];//0: root 1: odd 2: even 3: out of forest
bool flag;
bool vis[222];
bool shr[222];
int num;//scanfで直接入れる
void dfs(int node)
{
	if (vis[node])return;
	vis[node] = true;
	if (flag)return;
	for (int i = 0; i < pat[node].size(); i++)
	{
		if (flag)return;
		if (state[pat[node][i]] == 3)
		{
			par[pat[node][i]] = node;
			state[pat[node][i]] = 1;
			state[match[pat[node][i]]] = 2;
			dfs(match[pat[node][i]]);
		}
		else if (state[pat[node][i]] % 2 == 0)
		{
			if (root[node] == root[pat[node][i]])continue;
			vector<int>p1, p2;
			int v1 = node, v2 = pat[node][i];
			for (;;)
			{
				p1.push_back(v1);
				if (state[v1] == 0)break;
				p1.push_back(match[v1]);
				v1 = par[match[v1]];
			}
			for (;;)
			{
				p2.push_back(v2);
				if (state[v2] == 0)break;
				p2.push_back(match[v2]);
				v2 = par[match[v2]];
			}
			if (v1 != v2)
			{
				flag = true;
				reverse(p1.begin(), p1.end());
				reverse(p2.begin(), p2.end());
				for (int i = 0; i < p1.size() - 1; i += 2)
				{
					match[p1[i]] = p1[i + 1];
					match[p1[i + 1]] = p1[i];
				}
				for (int i = 0; i < p2.size() - 1; i += 2)
				{
					match[p2[i]] = p2[i + 1];
					match[p2[i + 1]] = p2[i];
				}
				match[node] = pat[node][i];
				match[pat[node][i]] = node;
				return;
			}
			else
			{
				reverse(p1.begin(), p1.end());
				reverse(p2.begin(), p2.end());
				int r = -1;
				for (int i = 0; i < min(p1.size(), p2.size()); i++)
				{
					if (p1[i] == p2[i])
					{
						r = root[p1[i]];
					}
				}
				int x1, x2;
				for (int i = 0; i < p1.size(); i++)if (root[p1[i]] == r)x1 = i;
				for (int i = 0; i < p2.size(); i++)if (root[p2[i]] == r)x2 = i;
				for (int i = x1 + 2; i < p1.size() - 1; i += 2)
				{
					par[p1[i]] = p1[i + 1];
				}
				for (int i = x2 + 2; i < p2.size() - 1; i += 2)
				{
					par[p2[i]] = p2[i + 1];
				}
				if (root[node] != r)par[node] = pat[node][i];
				if (root[pat[node][i]] != r)par[pat[node][i]] = node;
				vector<int>nxt;
				fill(shr, shr + num, false);
				for (int i = x1; i < p1.size(); i++)shr[root[p1[i]]] = true;
				for (int i = x2; i < p2.size(); i++)shr[root[p2[i]]] = true;
				for (int i = 0; i < num; i++)
				{
					if (shr[root[i]])
					{
						root[i] = r;
						if (state[i] == 1)
						{
							state[i] = 2;
							nxt.push_back(i);
						}
					}
				}
				for (int i = 0; i < nxt.size(); i++)dfs(nxt[i]);
			}
		}
	}
}
void maxmatching()//patに双方向に辺を入れて呼ぶとmatch[i]に最大マッチングでのマッチング相手が入る
{
	for (int i = 0; i < num; i++)match[i] = i;
	for (;;)
	{
		for (int i = 0; i < num; i++)
		{
			if (match[i] == i)state[i] = 0;
			else state[i] = 3;
			root[i] = par[i] = i;
			vis[i] = false;
		}
		flag = false;
		for (int i = 0; i < num; i++)
		{
			if (state[i] == 0)dfs(i);
		}
		if (!flag)break;
	}
}
int main()
{
	int way;
	scanf("%d%d", &num, &way);
	for (int i = 0; i < way; i++)
	{
		int za, zb;
		scanf("%d%d", &za, &zb);
		za--, zb--;
		pat[za].push_back(zb);
		pat[zb].push_back(za);
	}
	maxmatching();
	int m = 0;
	for (int i = 0; i < num; i++)if (match[i] == i)m++;
	int r = root[0];
	int cnt = 0;
	for (int i = 0; i < num; i++)if (root[i] == r)cnt++;
	if (m == 1 && cnt >= 3)printf("Yes\n");
	else printf("No\n");
}