题意分析

1.问题背景： 京都的街道按照棋盘式布局（中国传统的城市规划模式），分为南北走向（NS）或东西走向（EW）。两条正交的街道（即一条NS和一条EW）会形成一个交叉路口，该路口的名称由两条街道的名称组合而成，格式为X-Y。关键在于确定名称的顺序：

**名称的顺序反映了街道的“强弱”关系。**例如： Shijo-Kawaramachi（EW在前）表示Shijo比Kawaramachi强。 Kawaramachi-Sanjo（NS在前）表示Kawaramachi比Sanjo强。 2.输入：

输入是一个数据集序列，每个数据集包含： N：已知交叉路口的数量。 N个交叉路口名称（格式为X-Y）。 M：需要验证的交叉路口名称数量。 M个待验证的交叉路口名称（格式为X-Y）。 数据集以N=0结束。 3.输出：

对于每个数据集，输出： 第一行：已知交叉路口中涉及的不同街道数量。 接下来的M行：对于每个待验证的交叉路口名称，输出YES或NO： YES：可以推断两条街道正交，且X比Y强。 NO：无法满足上述条件。 强弱关系定义： 两条街道A和B等强（记为$A ≈ B$）当且仅当： (1)它们都与同一条街道C交叉（即A-C和B-C在输入中）。 (2)不存在街道D使得D-A和B-D在输入中。 (3)不存在街道E使得A-E和E-B在输入中。 强弱关系的传递性： 如果存在序列$A = A₁, A₂, ..., Aₙ = B（n ≥ 2）$，且对任意i，Aᵢ-Aᵢ₊₁是输入中的交叉路口或$Aᵢ ≈ Aᵢ₊₁$，则A比B强（记为A > B）。

解题思路

1.输入处理： 读取已知交叉路口名称，解析出两条街道的名称。 为每条街道分配唯一ID，并记录所有街道名称。 2.构建强弱关系图： 初始化一个邻接矩阵table，表示街道之间的强弱关系： $table[i][j] = 1：$i比j强（直接输入）。 $table[i][j] = 2$：i和j等强（通过check函数验证）。 $BIG_NUM：$初始值，表示无直接关系。 3.Floyd-Warshall算法： 使用Floyd-Warshall算法计算传递闭包，更新table矩阵： 如果i > k且k > j，则i > j。 如果i ≈ k且k ≈ j，则i ≈ j。 4.验证待查询交叉路口： 对于每个查询X-Y： 检查X和Y是否正交（即X和Y的走向不同，且X-Y或Y-X在输入中）。 检查X > Y（即$table[X][Y]$%$2 == 1$）。

代码实现

#include <stdio.h>
#include <cmath>
#include <algorithm>
#include <cfloat>
#include <stack>
#include <queue>
#include <vector>
#include <string>
#include <iostream>
#include <set>
#include <map>
#include <time.h>
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define MOD 1000000007
#define EPS 0.000000001
using namespace std;


struct Info{
	char name[20];
};

int N,table[200][200],index;
Info info[200];

bool strCmp(char* base, char* comp){
	int length1,length2;
	for(length1=0;base[length1] != '\0';length1++);
	for(length2=0;comp[length2] != '\0';length2++);
	if(length1 != length2)return false;
	
	for(int i=0;base[i] != '\0'; i++){
		if(base[i] != comp[i])return false;
	}
	return true;
}

void strcpy(char* to,char* str){
	for(int i=0;str[i] != '\0';i++){
		to[i] = str[i];
		to[i+1] = '\0';
	}
}

bool check(int A,int B){
	
	bool FLG = false;
	
	for(int k = 0; k < index; k++){
		if(k == A || k == B)continue;
		
		if((table[k][A] == 1 && table[k][B] == 1) || (table[A][k] == 1 && table[B][k]== 1)){
			FLG = true;
		}else if((table[k][A] == 1 && table[B][k] == 1) || (table[A][k] == 1 && table[k][B] == 1)){
			return false;
		}
	}
	
	return FLG;
}

void func(){
	
	for(int i = 0; i < 200; i++){
		for(int k = 0; k < 200; k++){
			table[i][k] = BIG_NUM;
		}
	}
	
	index = 0;
	int work_index,left_id,right_id,start;
	char buf[40],work[20];
	
	bool FLG;
	
	for(int i = 0; i < N; i++){
		scanf("%s",buf);
		for(work_index = 0; buf[work_index] != '-'; work_index++){
			work[work_index] = buf[work_index];
		}
		work[work_index] = '\0';
		
		FLG = false;
		for(int k = 0; k < index; k++){
			if(strCmp(info[k].name,work)){
				left_id = k;
				FLG = true;
				break;
			}
		}
		if(!FLG){
			left_id = index;
			strcpy(info[index].name,work);
			index++;
		}
		
		start = work_index+1;
		
		for(work_index = 0; buf[start+work_index] != '\0'; work_index++){
			work[work_index] = buf[start+work_index];
		}
		work[work_index] = '\0';
		
		FLG = false;
		
		for(int k = 0; k < index; k++){
			if(strCmp(info[k].name,work)){
				right_id = k;
				FLG = true;
				break;
			}
		}
		if(!FLG){
			right_id = index;
			strcpy(info[index].name,work);
			index++;
		}
		table[left_id][right_id] = 1;
	}
	
	for(int i = 0; i < index-1; i++){
		for(int k = i+1; k < index; k++){
			if(check(i,k)){
				table[i][k] = 2;
				table[k][i] = 2;
			}
		}
	}
	
	for(int mid = 0; mid < index; mid++){
		for(int start = 0; start < index; start++){
			if(table[start][mid] == BIG_NUM)continue;
			for(int goal = 0; goal < index; goal++){
				if(table[mid][goal] == BIG_NUM)continue;
				table[start][goal] = min(table[start][goal],table[start][mid]+table[mid][goal]);
			}
		}
	}
	
	printf("%d\n",index);
	
	int M;
	scanf("%d",&M);
	
	for(int loop = 0; loop < M; loop++){
		scanf("%s",buf);
		for(work_index = 0; buf[work_index] != '-'; work_index++){
			work[work_index] = buf[work_index];
		}
		work[work_index] = '\0';
		
		FLG = false;
		for(int k = 0; k < index; k++){
			if(strCmp(info[k].name,work)){
				left_id = k;
				FLG = true;
				break;
			}
		}
		if(!FLG){
			printf("NO\n");
			continue;
		}
		
		start = work_index+1;
		
		for(work_index = 0; buf[start+work_index] != '\0'; work_index++){
			work[work_index] = buf[start+work_index];
		}
		work[work_index] = '\0';
		
		FLG = false;
		
		for(int k = 0; k < index; k++){
			if(strCmp(info[k].name,work)){
				right_id = k;
				FLG = true;
				break;
			}
		}
		
		if(!FLG){
			printf("NO\n");
			continue;
		}
		
		if(table[left_id][right_id]%2 == 1){
			printf("YES\n");
		}else{
			printf("NO\n");
		}
		
	}
	
}

int main(){
	
	while(true){
		scanf("%d",&N);
		if(N == 0)break;
		
		func();
	}
	
	return 0;
}