1074.cpp

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

/*  This Code is Submitted by wywcgs for Problem 1074 on 2006-02-10 at 14:53:10 */ 
#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX = 32;
const int S_MAX = 64;

class Line {
public:
	int stop[S_MAX], n;
	void make();
	inline int pos(int) const;
};
void Line::make() {
	for(n = 1; true; n++) {
		scanf("%d", &stop[n-1]);
		if(getchar() == '\n') break;
	}
}
inline int Line::pos(int dep) const {
	return stop[dep%n];
}

bool meet[MAX][MAX];

bool knowAll(int);

int main()
{
	Line line[MAX];
	int i, j, k;
	int n, d, s, drl[MAX], begin[MAX];

	while(scanf("%d %d %d", &n, &d, &s) != EOF && n != 0) {
		memset(meet, false, sizeof(meet));
		for(i = 0; i < n; i++) {
			line[i].make(); ungetc(' ', stdin);
			while(getchar() != '\n') {
				int o, b;
				scanf("%d %d", &b, &o); o--;
				for(j = 0; line[i].stop[j] != b; j++) ;
				drl[o] = i; begin[o] = j;
			}
		}
		for(i = 0; i < d; i++)
			for(j = 0; j < d; j++) {
				Line &li = line[drl[i]], &lj = line[drl[j]];
				int step = li.n * lj.n / __gcd(li.n, lj.n);
				for(k = 0; k < step; k++)
					if(li.pos(begin[i]+k) == lj.pos(begin[j]+k)) { meet[i][j] = meet[j][i] = true; break; }
			}
		printf("%s\n", knowAll(d) ? "Yes" : "No");
	}
	
	return 0;
}

bool knowAll(int n)
{
	bool vst[MAX] = { true };
	int i, stack[MAX], top = 0;
	stack[top++] = 0;
	while(top > 0) {
		int p = stack[--top];
		for(i = 0; i < n; i++)
			if(meet[i][p] && !vst[i]) vst[i] = true, stack[top++] = i;
	}
	for(i = 0; i < n; i++)
		if(!vst[i]) return false;
	return true;
}