AtCoder ARC #092 : F - Two Faced Edges

これはなかなか思いつかないな。
https://beta.atcoder.jp/contests/arc092/tasks/arc092_d

問題

N頂点M辺の有向グラフが与えられる。
各辺について、その向きを逆にした場合連結成分数が変化するか判定せよ。

解法

辺の両端をA→Bとし、向きを逆にしてB→Aとする場合を考える。
元のグラフに関し、以下の２つの条件を考える。

• A→Bの辺を除いてもA→Bへのパスがある
• B→Aのパスがある

上記をどちらも満たさない場合、A,Bは辺の向きに関わらず異なる連結成分だし、両方満たす場合は向きに関わらず同一の連結成分となり、連結成分数は変化しない。
前者を満たし後者を満たさない場合は向きを逆にすると連結成分数が減るし、後者を満たし前者を満たさない場合は向きを逆にすると連結成分数が増える。

よって、上記２条件の片方だけを満たすかどうかをチェックすればよい。
後者の条件は各頂点から1回ずつBFSなりDFSを行えばいいのでよい。

問題は前者の条件である。
始点が同じAである辺をまとめて処理しよう。
Aから各頂点へのパスについて、Aから伸びる辺を最初の1回だけ使う条件のもとで、２通り以上あるかを考える。
例えばA→Bという辺があったとき、A→Bに至るパスのうち最初に使う辺の取り方が２通り以上あるなら、「A→Bの辺を除いてもA→Bへのパスがある」を満たすことになる。

２通り以上のカウントの仕方だが、以下のようにダイクストラの要領で求められる。
Aから伸びる辺が異なる番号を持つとする。各頂点へのパスにおいて、各頂点最初に選んだ辺の番号の最小値を覚えるようにしてダイクストラ法を適用しよう。
同様に、辺の番号の最大値を覚えるようにしてダイクストラ法を適用する。
２本以上最初に選択できる辺があるなら、この最小値と最大値は異なっているはずであり、そこから最初の辺の取り方が２通り以上あることがわかる。

int N;
vector<int> E[1010];
int M;
int ID[1010][1010];
int G[1010][1010];
int P[1010][1010];
int D[2][1010];
int A[202020],B[202020];

void dfs(int cur,int org) {
	G[org][cur]=1;
	FORR(e,E[cur]) if(G[org][e]==0) dfs(e,org);
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	MINUS(ID);
	
	FOR(i,M) {
		cin>>A[i]>>B[i];
		A[i]--;
		B[i]--;
		E[A[i]].push_back(B[i]);
		ID[A[i]][B[i]]=i;
	}
	
	FOR(i,N) dfs(i,i);
	FOR(i,N) {
		FOR(j,2) {
			FOR(x,N) D[j][x]=-1<<30;
			priority_queue<pair<int,int>> PQ;
			FOR(x,N) if(ID[i][x]>=0) {
				D[j][x]=ID[i][x];
				if(j) D[j][x]=-D[j][x];
				PQ.push({D[j][x],x});
			}
			
			while(PQ.size()) {
				int cur=PQ.top().second;
				int sc=PQ.top().first;
				PQ.pop();
				
				if(D[j][cur]!=sc) continue;
				FORR(e,E[cur]) if(D[j][e]<sc) {
					if(e==i) continue;
					D[j][e]=sc;
					PQ.push({sc,e});
				}
			}
		}
		FOR(x,N) {
			if(D[0][x]!=-1<<30 && D[0][x]!=-D[1][x]) P[i][x]=1;
		}
	}
	
	FOR(i,M) {
		if(P[A[i]][B[i]]==G[B[i]][A[i]]) cout<<"same"<<endl;
		else cout<<"diff"<<endl;
	}
	
	
	
}

まとめ

色々思いつくものだな…。