Croatia OI 2007 - policija

問題文 : POLICIJA

問題概要 :

無向連結グラフが与えられる. 以下のようなクエリに答えよ.

• 頂点 $u, v$ と辺 $e$ に対し, $e$ を取り除いたとき $u$ から $v$ へ辿り着けるか？
• 頂点 $u,\ v,\ w$ に対し, $w$ を取り除いたとき $u$ から $v$ へ辿り着けるか？

解法 :

Euler-tour のように辺に番号付けをするdfs を前計算として行い, その過程で各頂点のlowlink を求める. (O(N + E))
すると, 各クエリにO(log N) で答えられるため, 計算量は全体でO(N + E + Qlog N) となる.

各クエリの答えは次のようになる.

• 頂点 $u, v$ と辺 $e$ に対し, $e$ を取り除いたとき $u$ から $v$ へ辿り着けるか？

eを結ぶ頂点v1, v2 のうち, dfs を行った際の祖先(ancestor) になっているものをv1 とすると, 以下のときu からv へ辿れる.

• depth[v1] + 1 != depth[v2] のとき

深さが異なるので, たとえu と v がe の経路上にあってもdepth[v2] -> depth[v2] - 1 ... -> depth[v1] となるように頂点をたどればお互いに辿り着ける.

• u が v2 の子孫(decendant) であるかないかの状態がv と同じであるとき

どちらもv2 の子孫であれば, v2 を介して合流できる. また, 子孫でなければv2 に行かなくていいので辺がなくなっても困らない.

• low[v2] < ord[v2] のとき

ord[w] == low[v2]となる頂点から迂回すれば良い.

逆に, 上の3 つの状態でなければ𝑢 から 𝑣 へ辿り着けるない.

• 頂点$u,\ v,\ w$ に対し, $w$ を取り除いたとき $u$ から $v$ へ辿り着けるか？

こっちはhos さんのスライドを参照しました.

テストケースが無いので自分で簡単にチェックしたくらいです. 撃墜されないかこわい...

=> SPOJ でジャッジ出来ました(WA していたのでコードを済み)

コード :

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> G[100000];
vector<int> T[100000];
bool vis[100000];
int ord[100000], fin[100000], low[100000];
int depth[100000];

void dfs(int v, int p, int d, int &k)
{
	vis[v] = true;
	low[v] = ord[v] = k++;
	depth[v] = d;
	
	for (int i = 0; i < G[v].size(); i++){
		if (!vis[G[v][i]]){
			dfs(G[v][i], v, d + 1, k);
			T[v].push_back(G[v][i]);
			low[v] = min(low[v], low[G[v][i]]);
		}
		else if (G[v][i] != p){
			low[v] = min(low[v], ord[G[v][i]]);
		}
	}
	
	fin[v] = k++;
}

bool isDecendant(int u, int v) //頂点u は頂点v の子孫か?
{
	return (ord[v] <= ord[u] && fin[u] <= fin[v]);
}

int findChild(int u, int v) //u の子でv を子に持つものを探す (v is decendant of u)
{
	int left = 0, right = T[u].size() - 1;
	
	while (left != right){
		int center = (left + right) / 2;
		if (ord[v] > fin[T[u][center]]) left = center + 1;
		else if (fin[v] < ord[T[u][center]]) right = center - 1;
		else left = right = center;
	}
	return (T[u][left]);
}

int main()
{
	int N, E, Q;
	
	scanf("%d %d", &N, &E);
	
	for (int i = 0; i < E; i++){
		int u, v;
		scanf("%d %d", &u, &v);
		G[--u].push_back(--v);
		G[v].push_back(u);
	}
	
	int k = 0;
	dfs(0, -1, 0, k);
	
	scanf("%d", &Q);
	
	for (int i = 0; i < Q; i++){
		int Qtype, u, v;
		
		scanf("%d %d %d", &Qtype, &u, &v);
		--u; --v;
		
		if (Qtype == 1){
			int v1, v2;
			scanf("%d %d", &v1, &v2);
			--v1; --v2;
			
			if (isDecendant(v1, v2)) swap(v1, v2); //v1 is always ancestor
			
			if (depth[v1] + 1 != depth[v2] ||
				isDecendant(u, v2) == isDecendant(v, v2) ||
				low[v2] < ord[v2]){
				printf("yes\n");
			}
			else {
				printf("no\n");
			}
		}
		else {
			int w;
			scanf("%d", &w);
			--w;
			
			if (!isDecendant(u, w) && !isDecendant(v, w)) printf("yes\n");
			else {
				if (isDecendant(v, w)) swap(u, v);
				int pu, pv = -1;
				
				pu = findChild(w, u);
				if (isDecendant(v, w)) pv = findChild(w, v);
				
				if (pu == pv ||
					(pv == -1 && low[pu] < ord[w]) ||
					(low[pu] < ord[w] && low[pv] < ord[w])){
					printf("yes\n");
				}
				else {
					printf("no\n");
				}
			}
		}
	}
	
	return (0);
}