旅行会社 [yukicoder 416] - はまやんはまやんはまやん

問題

N頂点、M辺の無向グラフがある。
これからQ回のイベントを順に処理する。
1つのイベントで頂点Ciと頂点Diを結ぶ辺が壊される。

この時、何回目のイベントで頂点1から頂点iまでが連結じゃなくなったかを出力せよ。
ただし、辺が全て壊されても連結なら-1、元々連結じゃないなら0を出力。

2 <= N <= 10^5
1 <= M <= 2 * 10^5
1 <= Q <= M

考察

1. クエリの問題はまとめてやることで計算量を落とせたりする
2. こういう順番にやる問題 + 消してく -> 逆からやっていくとうまくいく印象
3. 逆から考えていくかなーと考えていくと分かる
4. あと、連結を考えるので、とりあえずUnion-Findかな？？って感じ

5. まず全部の辺が壊された状態でUnion-Findを作る
6. この時点で頂点0と連結なやつは-1、連結じゃないやつはQを入れる
7. ここから破壊された辺を1つずつ復元していき、連結判定すればいい
8. …ん？ここ結構時間かかる？
9. この解法O(n^2)なんけ。だめやん

10. 別の解法を考えると、今回は頂点1からの連結性を考えるため、DFSやダイクストラ的な感じもある
11. そっち方面で考える
12. ダイクストラ的な解法だ！

ans[i] = 頂点1と頂点iが連結じゃなくなるイベントは何回目か？
最初は ans[1] = INF, ans[他] = 0
ans[i]が大きいものからpriority_queueで取得し処理する
ある頂点iを処理するとき、全ての辺での遷移先jに対して、ans[j] = max(ans[j], min(ans[i], E[i][j]))を計算していく
E[i][j]は頂点iと頂点jが壊されるイベントが何回目かが入ってる（壊されなければINF）
処理をこれで進めていき、最後にansの中でINFのものを-1にして出力する

13. 似たような問題をCodeforcesだかで見た気がする

実装

http://yukicoder.me/submissions/113689

#define INF INT_MAX/2
int N, M, Q;
map<int, int> E[101010];
int ans[101010];
bool done[101010];
//-----------------------------------------------------------------
int main() {
	cin >> N >> M >> Q;
	rep(i, 0, M) {
		int A, B;
		scanf("%d %d", &A, &B);
		E[A][B] = INF;
		E[B][A] = INF;
	}

	rep(i, 0, Q) {
		int C, D;
		scanf("%d %d", &C, &D);
		E[C][D] = i + 1;
		E[D][C] = i + 1;
	}

	priority_queue<pair<int, int> > que;
	ans[1] = INF;
	que.push(make_pair(INF, 1));
	while (!que.empty()) {
		auto q = que.top(); que.pop();

		int c = q.first;
		int i = q.second;

		if (done[i]) continue;
		done[i] = true;

		for (auto p : E[i]) {
			int j = p.first;
			int cc = p.second;
			if (ans[j] < min(ans[i], cc)) {
				ans[j] = min(ans[i], cc);
				que.push(make_pair(ans[j], j));
			}
		}
	}

	rep(i, 2, N+1) {
		if (ans[i] == INF)
			printf("-1\n");
		else
			printf("%d\n", ans[i]);
	}
}