Submission #2230695

---

Source Code Expand

#include <map>
#include <set>
#include <queue>
#include <cstdio>
#include <algorithm>

using namespace std;

#define fir first
#define sec second

typedef pair<int, int> PI;

namespace io
{
	const int maxb = 1 << 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;
	}
}

int Getint()
{
	using namespace io;
	char ch;
	while (Getchar(ch) && (ch < '0' || ch > '9'));
	int s = ch - '0';
	while (Getchar(ch) && ch >= '0' && ch <= '9')
		s = s * 10 + ch - '0';
	return s;
}

const int maxn = 1e5 + 10;

set<int> adj[maxn];
map<int, int> cnt[maxn];

int main()
{
	int n = Getint(), m = n - 1 << 1;
	for (int i = 1; i <= m; ++ i)
	{
		int x = Getint(), y = Getint();
		if (x > y) swap(x, y);
		adj[x].insert(y);
		adj[y].insert(x);
		++ cnt[x][y];
	}
	queue<PI> Q;
	for (int i = 1; i <= n; ++ i)
	{
		for (set<int> :: iterator it = adj[i].begin(); it != adj[i].end(); ++ it)
		{
			if (*it > i) break;
			if (cnt[*it][i] > 1) Q.push(PI(*it, i));
		}
	}
	int count = 0;
	while (!Q.empty())
	{
		int x = Q.front().fir, y = Q.front().sec;
		Q.pop();
		if (adj[x].empty() || adj[y].empty()) continue;
		++ count;
		adj[x].erase(y);
		adj[y].erase(x);
		if (adj[x].size() < adj[y].size()) swap(x, y);
		for (set<int> :: iterator it = adj[y].begin(); it != adj[y].end(); ++ it)
		{
			adj[*it].erase(y);
			adj[*it].insert(x);
			adj[x].insert(*it);
			int p = min(x, *it), q = max(x, *it);
			if ((cnt[p][q] += cnt[min(y, *it)][max(y, *it)]) == 2) Q.push(PI(p, q));
		}
		adj[y].clear();
	}
	if (count == n - 1) puts("YES"); else puts("NO");
	return 0;
}

Submission Info

Judge Result