kmjp's blog

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

AtCoder ARC #045 : D - みんな仲良し高橋君

ARC

これは本番中に解けなくても仕方ないかな…。
http://arc045.contest.atcoder.jp/tasks/arc045_d

問題

２次元座標上に(2*N+1)個の格子点の位置が与えられる。
各頂点を除いたとき、残りの2N頂点を同じX座標または同じY座標を持つ異なる頂点のペアN組に分類出来るか判定せよ。

解法

同じX座標またはY座標を持つ頂点群を、まずUnion-Findで連結してみる。
この時、連結頂点群の頂点数が偶数ならば、その頂点群からその半数のペアを構築可能である。
(証明はEditorial参照)

そのため、問題の条件を満たすには、1個頂点を除いた結果、残りの頂点群は、頂点が偶数のからなる連結頂点群だけであればよい。
まず、頂点数が奇数の連結頂点群が２個以上あるとき、常に条件を満たせない。

頂点数が奇数の連結頂点群が１個あるとき、その中の１個を取り除くことで、条件を満たせる可能性がある。
(他の頂点数が偶数の連結頂点群から点を取り除くと、頂点数が奇数の連結頂点群が残るので常に条件を満たせない)

あとは、頂点数が奇数の連結頂点群中の各頂点において、取り除いたときに条件を満たすか判定すればよい。

そこで以下のような無向グラフを考える。
同じX座標またはY座標にある頂点群をリング状に辺を張る。
これは１点なくなっても、他の点はペアを構築可能であり、グラフとしては連結で有り続けるためである。
Editorialの例とは少し違うが、上記条件を満たすという意味では狙いは同じである。

次に、二重頂点連結成分分解を行い、関節点を求める。
関節点でない頂点は、取り除くと残りの頂点は頂点数が偶数の連結頂点群を成すので、問題の条件を満たす。
関節点である頂点は、取り除いたときに残りの頂点が成す複数の連結頂点群が、いずれも偶数頂点からなるなら、問題の条件を満たす。

偶数頂点条件の判定は、以下のように行う。

  • 全頂点数は奇数なので、取り除く対象の頂点を除けば偶数。よって各subtreeが偶数頂点であるか判定すれば、親側は判定不要。
  • 二重頂点連結成分分解の過程で、頂点vの子頂点uの訪問順num(u)とlowlink値low(u)に対し、low(u)==num(u)が成り立つなら、その子頂点の先の成分は親側と連結しない。
    • 子頂点uのDFS処理後の訪問頂点数とnum(u)を比較することで、uのsubtree中の頂点数がわかるので、偶奇判定できる。

上記処理は二重頂点連結成分分解のDFSのついでに行える。


まとめると、頂点の連結処理後、奇数頂点からなる連結成分について二重頂点連結成分分解を行いつつ、関節点に対し各subtreeが偶数頂点で構成されるか判定すればよい。
…と書くと１行だが、自分は二重頂点連結成分分解のライブラリを持ってなかったので結構手こずった。

int N;
int X[202020],Y[202020];
vector<int> VX[202020],VY[202020];
int mp[202020],rev[202020],nt;
int ok[202020];

template<int um> class UF {
	public:
	vector<int> par,rank,cnt;
	UF() {par=rank=vector<int>(um,0); cnt=vector<int>(um,1); for(int i=0;i<um;i++) par[i]=i;}
	void reinit() {int i; FOR(i,um) rank[i]=0,cnt[i]=1,par[i]=i;}
	int operator[](int x) {return (par[x]==x)?(x):(par[x] = operator[](par[x]));}
	int count(int x) { return cnt[operator[](x)];}
	int operator()(int x,int y) {
		if((x=operator[](x))==(y=operator[](y))) return x;
		cnt[y]=cnt[x]=cnt[x]+cnt[y];
		if(rank[x]>rank[y]) return par[x]=y;
		rank[x]+=rank[x]==rank[y]; return par[y]=x;
	}
};
UF<202020> uf;

class SCC_ART {
public:
	static const int MV = 202020;
	int NV,time;
	vector<vector<int> > E;
	vector<int> low,num,isart,gr,index;
	vector<vector<int> > SC; // out
	vector<int> ART; // out
	UF<MV> uf;
	
	void init(int NV=MV) { this->NV=NV; E.clear(); E.resize(NV);}
	void add_edge(int x,int y) { E[x].push_back(y); E[y].push_back(x);}
	void dfs(int cur,int pre) {
		low[cur]=num[cur]=++time;
		int odd=0;
		FORR(e,E[cur]) {
			if(num[e]) low[cur]=min(low[cur],num[e]);
			else {
				int now=time;
				dfs(e,cur);
				low[cur]=min(low[cur],low[e]);
				if((num[cur]==1&&num[e]>2) || (num[cur]!=1&&low[e]>=num[cur])) isart[cur]=1;
				if(low[e]>=num[cur] && (time-now)%2) odd=1;
			}
		}
		if(isart[cur]) ART.push_back(cur);
		if(isart[cur] && odd) ok[mp[cur]]=0;
	}
	void scc() {
		ART.clear();uf.reinit();SC.clear();
		low=num=isart=gr=index=vector<int>(NV,0);
		for(int i=0;i<NV;i++) if(!num[i]) time=0,dfs(i,-1);
		sort(ART.begin(),ART.end());
		for(int i=0;i<NV;i++) FORR(r,E[i]) if(isart[i]==0 && isart[r]==0) uf(i,r);
		for(int i=0;i<NV;i++) if(uf[i]==i) gr[i]=SC.size(), SC.push_back(vector<int>());
		for(int i=0;i<NV;i++) gr[i]=gr[uf[i]], SC[gr[uf[i]]].push_back(i);
	}
};

SCC_ART scc;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	N=2*N+1;
	FOR(i,N) {
		cin>>X[i]>>Y[i];
		X[i]--, Y[i]--;
		if(VX[X[i]].size()) uf(VX[X[i]][0],i);
		if(VY[Y[i]].size()) uf(VY[Y[i]][0],i);
		VX[X[i]].push_back(i);
		VY[Y[i]].push_back(i);
	}
	
	int odd=-1;
	FOR(i,N) if(uf[i]==i && uf.count(i)%2==1) {
		if(odd==-1) odd=i;
		else {
			FOR(i,N) _P("NG\n");
			return;
		}
	}
	FOR(i,N) if(uf[i]==uf[odd]) mp[nt]=i, rev[i]=nt, nt++, ok[i]=1;
	scc.init(nt);
	
	FOR(i,N) {
		if(VX[i].size()>1 && uf[VX[i][0]]==uf[odd]) {
			FOR(j,VX[i].size()) scc.add_edge(rev[VX[i][j]],rev[VX[i][(j+1)%VX[i].size()]]);
		}
		if(VY[i].size()>1 && uf[VY[i][0]]==uf[odd]) {
			FOR(j,VY[i].size()) scc.add_edge(rev[VY[i][j]],rev[VY[i][(j+1)%VY[i].size()]]);
		}
	}
	
	scc.scc();
	
	FOR(i,N) _P("%s\n",ok[i]?"OK":"NG");
	
}

まとめ

二重頂点連結成分分解、二重辺よりはラクだね。