南郵 OJ 1949 比賽成績排序問題

比賽成績排序問題

時間限制(普通/Java) :  1000 MS/ 3000 MS          運作記憶體限制 : 65536 KByte

總送出 : 256            測試通過 : 47 

比賽描述

       所有題目（Word、PDF格式）：http://acm.njupt.edu.cn/acmhome/nuptacm/2013HW.zip

2013“華為杯”南京郵電大學大學生團體歌唱大賽比賽形式為：大賽分為多輪，每一輪随機選擇參賽團體進行兩兩PK賽。當根據多輪多場的PK賽成績能夠确定排名次序時，大賽結束。

我們将問題進行簡化，從1開始按遞增順序給每一個參賽團體配置設定一個整數編号，已知多場PK賽成績，請你根據勝負關系确定兩個給定參賽團體之間的成績排名次序。舉一個例子，參賽團體1在PK賽中勝參賽團體3，參賽團體2在PK賽中勝參賽團體1，則可知參賽團體2的成績比參賽團體3的成績排名高。

輸入

輸入包括多個行：

l         第1行給出參賽團體總數M、已知PK賽成績的場次C；

l         接下來有C行，每一行先後給出兩個參賽團體編号p和q，表示編号為p的參賽團體在PK賽中勝編号為q的參賽團體；

l         最後1行先後給出兩個參賽團體編号x和y。

這裡1≤M≤1000，1≤C≤10000，1≤p≤1000，1≤q≤1000，1≤x≤1000，1≤y≤1000，p≠q，x≠y。

輸出

針對問題輸入最後一行先後給出兩個參賽團體編号x和y，輸出1行，表示編号為x的參賽團體和編号為y的參賽團體之間的成績先後次序，具體規定如下：

l         編号為x的參賽團體的成績排名比編号為y的參賽團體高，則輸出x；

l         編号為y的參賽團體的成績排名比編号為x的參賽團體高，則輸出y；

l         不能确定編号為x的參賽團體和編号為y的參賽團體之間的成績先後次序，則輸出字元串N/A。

樣例輸入

3 2

1 3

2 1

2 3

樣例輸出

2

提示

本題純屬虛構，題目中輸入資料和輸出資料在一行中均以空格分隔，賽後酌情進行重新測試。

題目來源

SED

#include<iostream>

#define MAX_M 1001
bool a[MAX_M][MAX_M];
bool vst[MAX_M];
int M;

bool dfs(int x, int y){
	int z;
	if(a[x][y]){
		return 1;
	}
	vst[x] = 1;
	for(z=1;z<=M;z++){
		if(!vst[z] && a[x][z] && dfs(z,y)){
			vst[x] = 0;
			return 1;
		}
	}
	vst[x] = 0;
	return 0;
}

int main(){
	int C,x,y;
	scanf("%d%d",&M,&C);
	while(C--){
		scanf("%d%d",&x,&y);
		a[x][y] = 1;
	}
	scanf("%d%d",&x,&y);
	if(dfs(x,y)){
		printf("%d\n",x);
	}else if(dfs(y,x)){
		printf("%d\n",y);
	}else{
		printf("N/A\n");
	}
}