kmjp's blog

競技プログラミング参加記です

Codeforces #375 Div2 E. One-Way Reform

Fの方が簡単?
http://codeforces.com/contest/723/problem/E

問題

無向グラフが与えられる。
各辺に向きを付け有向グラフにしたい。
その際、入次数と出次数が等しい頂点数を最大にしたい。

最大で何頂点そのような点を作れるか。また、その際の辺の向きを答えよ。

解法

全頂点が連結で、かつ次数が偶数ならオイラー閉路を求めれば全頂点で条件を満たせる。
元のグラフに辺を足し、そのような形状にしよう。

とはいえ手順は簡単で、次数が奇数の点が偶数個あるはずなので、まずそれらを2つずつ対にして辺を1個追加しよう。
また、グラフが非連結の場合、例えば0番の頂点と非連結な連結成分があれば、0番の頂点と後者の連結成分の1頂点の間に2本辺を張ろう。

後はこの状態のグラフに対しオイラー閉路を求めればよい。
元の次数が奇数個の点は条件を満たせないが、それ以外の頂点は入次数と出次数が等しくなる。

template<int um> class UF {
	public:
	vector<int> par,rank;
	UF() {rank=vector<int>(um,0); for(int i=0;i<um;i++) par.push_back(i);}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};

template<int MV> class UndirectedEulerPath {
public:
	vector<int> path;
	multiset<int> E[MV];
	void add_path(int x,int y) { E[x].insert(y); E[y].insert(x); }
	
	void dfs(int cur) {
		while(E[cur].size()) {
			int tar=*E[cur].begin();
			E[cur].erase(E[cur].begin());
			E[tar].erase(E[tar].find(cur));
			dfs(tar);
		}
		path.push_back(cur);
	}
	
	bool GetPath() {
		int fo=-1,odd=0,i,np=0;
		FOR(i,MV) {
			np += E[i].size();
			if(E[i].size()%2) odd++, fo=(fo==-1)?i:fo;
		}
		if(odd!=0 && odd!=2) return false;
		dfs(odd?fo:0);
		reverse(path.begin(),path.end());
		return path.size()==np/2+1;
	}
};

void solve() {
	int i,j,k,l,r,x,y; string s;
	int T,N,M;
	
	cin>>T;
	while(T--) {
		int mat[203][203]={};
		int E[203]={};
		ZERO(mat);
		UF<220> uf;
		
		cin>>N>>M;
		int ret=N;
		UndirectedEulerPath<205> uep;
		
		FOR(i,M) {
			cin>>x>>y;
			x--;
			y--;
			mat[x][y]=mat[y][x]=1;
			E[x]++;
			E[y]++;
			uf(x,y);
			uep.add_path(x,y);
		}
		
		int pre=-1;
		FOR(i,N) if(uep.E[i].size()%2==1) {
			ret--;
			if(pre==-1) {
				pre=i;
			}
			else {
				uep.add_path(pre,i);
				uf(pre,i);
				pre=-1;
			}
		}
		
		
		FOR(i,N) if(uf[i]!=uf[0]) {
			uep.add_path(0,i);
			uep.add_path(0,i);
			uf(0,i);
		}
		
		
		uep.GetPath();
		_P("%d\n",ret);
		FOR(i,(int)uep.path.size()-1) {
			if(mat[uep.path[i]][uep.path[i+1]]) {
				_P("%d %d\n",uep.path[i]+1,uep.path[i+1]+1);
				mat[uep.path[i]][uep.path[i+1]]=mat[uep.path[i+1]][uep.path[i]]=0;
			}
		}
	}
}

まとめ

入次数=出次数、という条件が出たらオイラー閉路を疑おう。