Submission #101864

---

Source Code Expand

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

#define rep(i, n) for(int i=0; i<int(n); i++)
#define mp make_pair
#define all(v) (v).begin(), (v).end()
typedef pair<int, int> PI;


#define MAX_N 100010

int par[MAX_N];
int rank[MAX_N];

int find(int x) {
	if (par[x] == x) return x;
	else
		return par[x] = find(par[x]);
}

void unite(int x, int y) {
	x = find(x);
	y = find(y);
	if (x == y) return;
	if (rank[x] < rank[y]) {
		par[x] = y;
	} else {
		par[y] = x;
		if (rank[x] == rank[y]) rank[x]++;
	}
}

bool same(int x, int y) {
	return find(x) == find(y);
}


int main() {
	int N, M, K;
	cin >> N >> M >> K;
	vector<PI> edges;
	rep(i, M) {
		int x, y; cin >> x >> y;
		x--, y--;
		edges.push_back(mp(x, y));
	}
	bool del[M];
	rep(i, M) del[i] = false;
	vector<pair<int, PI> > queries;
	rep(i, K) {
		int s; cin >> s;
		if (s == 0) {
			int e; cin >> e;
			e--;
			del[e] = true;
			queries.push_back(mp(s, edges[e]));
		} else {
			int v, w;
			cin >> v >> w;
			v--, w--;
			queries.push_back(mp(s, mp(v, w)));
		}
	}
	reverse(all(queries));

	rep(i, MAX_N)
		par[i] = i, rank[i] = 0;

	vector<bool> ans;
	rep(i, M) if (!del[i]) {
		unite(edges[i].first, edges[i].second);
	}

	rep(i, queries.size()) {
		if (queries[i].first == 0) {
			unite(queries[i].second.first, queries[i].second.second);
		} else {
			ans.push_back(same(queries[i].second.first, queries[i].second.second));
		}
	}

	reverse(all(ans));

	rep(i, ans.size()) {
		if (ans[i])
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}



}

Submission Info

Judge Result