Submission #101899

---

Source Code Expand

#include <iostream>
#include <cstring>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;

const int MAX_N = 100000;

struct Query
{
	bool type;
	int x,y;
};
typedef pair<int,int> Pii;

int par[MAX_N];
int rank[MAX_N];
Query q[MAX_N];

void init(int n)
{
	for (int i=0; i<n; i++)
	{
		par[i] = i;
		rank[i] = 0;
	}
}

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;

	bool use[M];
	memset(use, 0xff, sizeof(use));
	init(N);

	//edge
	Pii e[M];
	for (int i=0; i<M; i++)
	{
		cin >> e[i].first >> e[i].second;
		e[i].first--; e[i].second--;
		//cout << "edge" << i << ": " << e[i].first << ' ' << e[i].second << endl;
	}

	//query
	for (int i=0; i<K; i++)
	{
		cin >> q[i].type;
		if (!q[i].type)
		{
			cin >> q[i].x;
			q[i].x--;
			use[ q[i].x ] = 0;
		}
		else
		{
			cin >> q[i].x >> q[i].y;
			q[i].x--; q[i].y--;
		}
	}

	//final state
	for (int i=0; i<M; i++)
		if (use[i])
		{
			//cout << i << endl;
			unite(e[i].first, e[i].second);
			//cout << "un:" << e[i].first << ' ' << e[i].second << endl;
		}

	//reversely exec query reverse
	//cout << "---" << endl;
	vector<int> res;
	for (int i=K-1; i>=0; i--)
	{
		if (q[i].type)
		{
			res.push_back(same(q[i].x, q[i].y));
			//cout << "q:" << q[i].x << ' ' << q[i].y << ' ' << same(q[i].x, q[i].y) << endl;
		}
		else
		{
			//cout << q[i].x << endl;
			//cout << "un:" << e[q[i].x].first << ' ' << e[q[i].x].second << endl;
			unite(e[ q[i].x ].first, e[ q[i].x ].second);
		}
	}

	reverse(res.begin(), res.end());
	for (int i=0; i<res.size(); i++)
		cout << (res[i] ? "YES" : "NO") << endl;

}

Submission Info

Judge Result