2268.cpp

这是哈尔滨工业大学acmOJ的源代码

/*  This Code is Submitted by wywcgs for Problem 2268 on 2006-06-03 at 17:20:46 */ 
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;

typedef pair<int, int> pii;
const int QN = 20480;

class Ques {
public:
	int o[2], r[2], st;
	vector<pii> prev;
	void make(int);
};
Ques qu[QN];
void Ques::make(int to) {
	st = -1;
	scanf("%d %d %d %d", &o[0], &r[0], &o[1], &r[1]);
	qu[o[0]].prev.push_back(pii(to, 0));
	qu[o[1]].prev.push_back(pii(to, 1));
}

bool sol(int, int);

int main()
{
	int n, i;
	
	while(scanf("%d", &n) != EOF) {
		for(i = 0; i < n; i++) qu[i].prev.clear();
		for(i = 0; i < n; i++) qu[i].make(i);
		bool can = true;
		for(i = 0; i < n && can; i++)
			if(qu[i].st != -1) continue;
			else if(!sol(i, 0) && !sol(i, 1)) can = false;
		printf("%s\n", can ? "Yes" : "No");
	}
	
	return 0;
}

bool sol(int o, int r)
{
	if(qu[o].st != -1) return (qu[o].st == r);
	qu[o].st = r;
	bool can = true;
	int i;
	for(i = 0; i < 2 && can; i++) {
		int no = qu[o].o[i], nr = qu[o].r[i];
		if(i != r) nr = 1-nr;
		if(!sol(no, nr)) can = false;
	}
	for(i = 0; i < qu[o].prev.size() && can; i++) {
		pii p = qu[o].prev[i];
		int po = p.first, co = p.second, pr;
		if(qu[po].r[co] == r) pr = co;
		else pr = 1-co;
		if(!sol(po, pr)) can = false;
	}
	if(!can) qu[o].st = -1;
	return can;
}