1801.cpp

哈尔滨工业大学ACM 竞赛网上在线试题集锦的源代码

/* This Code is Submitted by wywcgs for Problem 1801 on 2006-11-10 at 21:42:55 */
#include <cstdio>
#include <cstring>
#include <map>
#include <algorithm>
using namespace std;
 
const int N = 256;
const int L = 20;
 
struct cmp {
	bool operator()(const char* s1, const char* s2) const
		{ return strcmp(s1, s2) < 0; }
};
 
class UFSet {
public:
	int parent[N];
	void clear() { memset(parent, -1, sizeof(parent)); }
	int find(int);
	void unionSet(int, int);
};
int UFSet::find(int x) {
	if(parent[x] == -1) return x;
	else return (parent[x] = find(parent[x]));
}
void UFSet::unionSet(int x, int y) {
	int px = find(x), py = find(y);
	if(px != py) parent[px] = py;
}
 
map<char*, int, cmp> cross;
char road[N][L];
int rn, label[N];
bool g[N][N];
 
int find(char*);
void dfs(int);
 
int main()
{
	int n, m;
	UFSet ufs;
	
	while(scanf("%d", &n) != EOF && n != 0) {
		rn = 0; cross.clear(); ufs.clear();
		memset(g, false, sizeof(g));
		for(int i = 0; i < n; i++) {
			char str1[L], str2[L];
			scanf("\n%[a-zA-Z0-9]-%[a-zA-Z0-9]", str1, str2);
			int o1 = find(str1), o2 = find(str2);
			g[o1][o2] = true; ufs.unionSet(o1, o2);
		}
		printf("%d\n", rn);
		memset(label, -1, sizeof(label));
		for(int i = 0; i < rn; i++)
			if(label[i] == -1) { label[i] = 0; dfs(i); }
		bool gx[N][N]; memcpy(gx, g, sizeof(g));
		for(int i = 0; i < rn; i++)
			for(int j = 0; j < rn; j++) {
				bool link = false, c = true;
				for(int k = 0; k < rn; k++) {
					if(gx[i][k] && gx[k][j]) c = false;
					if(gx[k][i] && gx[j][k]) c = false;
					if(gx[i][k] && gx[j][k]) link = true;
					if(gx[k][i] && gx[k][j]) link = true;
				}
				if(link && c) g[i][j] = g[j][i] = true;
			}
		for(int k = 0; k < rn; k++)
			for(int i = 0; i < rn; i++)
				for(int j = 0; j < rn; j++)
					g[i][j] |= g[i][k] & g[k][j];
		scanf("%d", &m);
		for(int i = 0; i < m; i++) {
			char str1[L], str2[L];
			scanf("\n%[a-zA-Z0-9]-%[a-zA-Z0-9]", str1, str2);
			int o1, o2;
			if(!cross.count(str1)) { printf("NO\n"); continue; }
			else o1 = cross.find(str1)->second;
			if(!cross.count(str2)) { printf("NO\n"); continue; }
			else o2 = cross.find(str2)->second;
			if(ufs.find(o1) != ufs.find(o2) || label[o1] == label[o2] || !g[o1][o2]) 
				printf("NO\n");
			else printf("YES\n");
		}
	}
 
	return 0;
}
 
int find(char* str)
{
	if(!cross.count(str)) {
		strcpy(road[rn], str);
		cross[road[rn]] = rn; rn++;
	}
	return cross.find(str)->second;
}
void dfs(int u)
{
	for(int i = 0; i < rn; i++) {
		if(!(g[u][i] || g[i][u]) || label[i] != -1) continue;
		label[i] = label[u]^1;
		dfs(i);
	}
}