小希的迷宫

cpp ▽
/**
 *    author: Akvicor
 *    created: 2019-06-13 17-17-53
**/

#include <bits/stdc++.h>

using namespace std;

#ifdef DEBUG
string to_string(string s) {
	return '"' + s + '"';
}

string to_string(const char* s) {
	return to_string((string) s);
}

string to_string(bool b) {
return (b ? "true" : "false");
}

template <typename A, typename B>
string to_string(pair<A, B> p) {
	return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}

template <typename A>
string to_string(A v) {
	bool first = true;
	string res = "{";
	for (const auto &x : v) {
		if (!first) {
			res += ", ";
		}
		first = false;
		res += to_string(x);
	}
	res += "}";
	return res;
}

void debug_out() { cerr << endl; }

template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
	cerr << " " << to_string(H);
	debug_out(T...);
}
#endif

#ifdef DEBUG
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 17
#endif

#ifdef DEBUG
#define FAST_IO 17
#define cout cout << "-->"
#else
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define endl '\n'
#endif

#define LL long long
#define ULL unsigned long long
#define rep(i, n) for(int i = 0; i < (n); ++i)
#define reep(i, n) for(int i = 0; i <= (n); ++i)
#define lop(i, a, n) for(int i = a; i < (n); ++i)
#define loop(i, a, n) for(int i = a; i <= (n); ++i)
#define ALL(v) (v).begin(), (v).end()
#define PB push_back
#define VI vector<int>
#define PII pair<int,int>
#define FI first
#define SE second
#define SZ(x) ((int)(x).size())

const double EPS = 1e-6;
const double PI = acos(-1.0);
const int INF = 0x3f3f3f3f;
const LL LINF = 0x7f7f7f7f7f7f7f7f;
const int MAXN = (int)1e6 + 10;
const int MOD = (int)1e9 + 7;

class UnionFind{
	private:
		int * parent;
		int * rank;
		bool * ral;
		int count;
	public:
		UnionFind(int n){
			parent = new int[n];
			rank = new int[n];
			ral = new bool[n];
			this->count = n;
			for(int i = 0; i < n; ++i){
				parent[i] = i;
				rank[i] = 1;
				ral[i] = false;
			}
		}
		~UnionFind(){
			delete[] parent;
			delete[] rank;
		}

		int find(int p){
			while(p != parent[p]){
				p = parent[p];
			}
			return p;
		}

		bool isConnected(int p, int q){
			this->ral[p] = true;
			this->ral[q] = true;
			return find(p) == find(q);
		}

		bool is_one_grap(){
			int res = 0;
			for(int i = 0; i <= this->count; ++i){
				if(this->parent[i] == i && this->ral[i]) ++res;
			}
			return res <= 1;
		}

		void unionElements(int p, int q){
			int pRoot = find(p);
			int qRoot = find(q);

			if(pRoot == qRoot) return;

			if(rank[pRoot] < rank[qRoot]){
				parent[pRoot] = qRoot;
			}else if(rank[qRoot] < rank[pRoot]){
				parent[qRoot] = pRoot;
			}else{
				parent[pRoot] = qRoot;
				rank[qRoot] += 1;
			}
		}

		int cnt(){
			int cnt = 0;
			for(int i = 0; i < this->count; ++i){
				if(parent[i] == i) ++cnt;
			}
			return cnt;
		}
};

int main(){
	FAST_IO;

	int p, q;
	
	while(true){
		bool flag = true;
		UnionFind uf = UnionFind(100010);
		while(cin >> p >> q){
			if(p == 0 && q == 0) break;
			if(p == -1 && q == -1) return 0;
			if(!flag) continue;
			if(uf.isConnected(p, q)) flag = false;
			else uf.unionElements(p, q);
		}
		if(flag && uf.is_one_grap()) cout << "Yes" << endl;
		else cout << "No" << endl;
	}

	return 0;
}