AtCoder ARC #039 : D - 旅行会社高橋君

後半パートは色々解き方ありそうね。
http://arc039.contest.atcoder.jp/tasks/arc039_d

問題

連結無向グラフが与えられる。

頂点A,B,CからなるクエリがQ個与えられる。
各クエリに対し、同一辺を複数回通らず、A→B→Cと移動可能か判定せよ。

解法

ある頂点対X→Yに移動する経路が複数あるのは、X,Yが二重辺連結成分分解後に連結成分であることである。
よってまずグラフを二重辺連結成分分解してしまおう。

二重辺連結成分分解をした後のグラフは木になる。
よってA→B→Cが同一辺を複数回通るかどうかは、A→BとC→Bが同じ辺を含むかどうか、という問題に還元できる。
以下木となったグラフについて考える。

まずAとBまたはBとCが連結している場合、そもそも(二重辺連結成分分解後の)辺を1個も辿らないので、A→BとC→Bは当然同じ辺を通らず、問題文の条件を満たす。

AとB、BとCが非連結の場合、同じ辺を通るかどうかはいくつか判定方法がある。

• A→Cの距離が(A→Bの距離)+(B→Cの距離)なら、同じ辺を通らない(BがA→Cの最短経路上にある)
• Bから見て、AとCが異なる子のサブツリー(またはBの親側)に含まれるなら、同じ辺を通らない。
• BからAに向けて頂点1個分移動した点と、BからCに向けて頂点1個分移動した点が異なるなら、同じ辺を通らない。

自分は本番は3つ目の方法を用いたが、以下は1つ目の解法のコード。

class SCC_BI {
public:
	static const int MV = 120000;
	vector<int> E[MV];
	stack<int> roots,S;
	int NV,ord[MV],llink[MV],inin[MV],time;
	vector<int> ART; // out
	vector<vector<int> > SC; // out
	vector<pair<int,int> > BR; // out 
	
	SCC_BI(int NV=MV) { this->NV=NV; for(int i=0;i<MV;i++) E[i].clear();}
	void add_edge(int x,int y) { E[x].push_back(y); E[y].push_back(x); }
	void dfs(int cur,int pre) {
		int art=0,conn=0,i;
		ord[cur]=llink[cur]=++time;
		S.push(cur); inin[cur]=1; roots.push(cur);
		FOR(i,E[cur].size()) {
			int tar=E[cur][i];
			if(ord[tar]==0) {
				conn++; dfs(tar,cur);
				llink[cur]=min(llink[cur],llink[tar]);
				art += (pre!=-1 && ord[cur]<=llink[tar]);
				if(ord[cur]<llink[tar]) BR.push_back(make_pair(min(cur,tar),max(cur,tar)));
			}
			else if(tar!=pre) {
				llink[cur]=min(llink[cur],ord[tar]);
				while(inin[tar]&&ord[roots.top()]>ord[tar]) roots.pop();
			}
		}
		
		if(cur==roots.top()) {
			SC.push_back(vector<int>());
			while(1) {
				i=S.top(); S.pop(); inin[i]=0;
				SC.back().push_back(i);
				if(i==cur) break;
			}
			sort(SC.back().begin(),SC.back().end());
			roots.pop();
		}
		if(art || (pre==-1&&conn>1)) ART.push_back(cur);
	}
	void scc() {
		SC.clear(),BR.clear(),ART.clear();
		ZERO(ord);ZERO(llink);ZERO(inin);time=0;
		for(int i=0;i<NV;i++) if(!ord[i]) dfs(i,-1);
		sort(BR.begin(),BR.end()); sort(ART.begin(),ART.end());
	}
};

int N,M,Q;
vector<int> E[101000];
SCC_BI scc;
int ID[101000];
int P[21][100005],D[100005];

void dfs(int cur) {
	ITR(it,E[cur]) if(*it!=P[0][cur]) D[*it]=D[cur]+1, P[0][*it]=cur, dfs(*it);
}
int dist(int a,int b) {
	int ret=0,i,aa=a,bb=b;
	if(D[aa]>D[bb]) swap(aa,bb);
	for(i=19;i>=0;i--) if(D[bb]-D[aa]>=1<<i) bb=P[i][bb];
	for(i=19;i>=0;i--) if(P[i][aa]!=P[i][bb]) aa=P[i][aa], bb=P[i][bb];
	return D[a]+D[b]-2*D[(aa==bb)?aa:P[0][aa]];
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	scc.NV=N;
	FOR(i,M) {
		cin>>x>>y;
		scc.add_edge(x-1,y-1);
	}
	
	scc.scc();
	FOR(i,scc.SC.size()) FORR(r,scc.SC[i]) ID[r]=i;
	FORR(r,scc.BR) E[ID[r.first]].push_back(ID[r.second]), E[ID[r.second]].push_back(ID[r.first]);
	dfs(0);
	FOR(i,19) FOR(x,N) P[i+1][x]=P[i][P[i][x]];

	cin>>Q;
	while(Q--) {
		cin>>x>>y>>r;
		if(dist(ID[x-1],ID[y-1])+dist(ID[y-1],ID[r-1])==dist(ID[x-1],ID[r-1])) cout<<"OK"<<endl;
		else cout<<"NG"<<endl;
	}
}

まとめ

無駄にややこしい解法しちゃったな。