首爾性愛美術館18禁的藝術女大生禁不起誘惑!按了..輕忽小中風,當心變殘障睽違25天終開會 立院...
2012-03-26 20:34:38 人氣(375) | 回應(0) | 推薦(0) | 收藏(0) 上一篇 | 下一篇

[UVA] 10227 - Forests

0
收藏
0
推薦

Problem D: Forests

If a tree falls in the forest, and there's nobody there to hear, does it make a sound? This classic conundrum was coined by George Berkeley (1685-1753), the Bishop and influential Irish philosopher whose primary philosophical achievement is the advancement of what has come to be called subjective idealism. He wrote a number of works, of which the most widely-read are Treatise Concerning the Principles of Human Knowledge (1710) and Three Dialogues between Hylas and Philonous (1713) (Philonous, the "lover of the mind," representing Berkeley himself).

A forest contains T trees numbered from 1 to T and P people numbered from 1 to P.

Input

The input begins with a single positive integer on a line by itself indicating the number of the cases following, each of them as described below. This line is followed by a blank line, and there is also a blank line between two consecutive inputs.

Standard input consists of a line containing P and T followed by several lines, containing a pair of integers i and j, indicating that person i has heard tree j fall. People may have different opinions as to which trees, according to Berkeley, have made a sound.

Output

For each test case, the output must follow the description below. The outputs of two consecutive cases will be separated by a blank line.

How many different opinions are represented in the input? Two people hold the same opinion only if they hear exactly the same set of trees. You may assume that P < 100 and T < 100.

Sample Input

1

3 4
1 2
3 3
1 3
2 2
3 2
2 4

Output for Sample Input

2

暴力檢查是否有些人都看到了某些樹都倒了

#include <stdio.h>
#include <string.h>
int main() {
int t, P, T;
char blank[200];
scanf("%d ", &t);
while(t--) {
scanf("%d %d ", &P, &T);
int PT[101][101] = {};
int i, j, k;
while(gets(blank)) {
if(strcmp(blank, "") == 0)
break;
sscanf(blank, "%d %d", &i, &j);
PT[i][j] = 1;
}
int ans = 0, used[101] = {};
for(i = 1; i <= P; i++) {
if(used[i] == 0) {
for(j = i+1; j <= P; j++) {
if(used[j] == 0) {
for(k = 1; k <= T; k++)
if(PT[i][k] != PT[j][k])
break;
if(k == T+1)
used[j] = 1;
}
}
ans ++;
}
}
printf("%d\n", ans);
if(t) puts("");
}
return 0;
}

10227Forests
台長:Morris
人氣(375) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA] 10025 - The ? 1 ? 2 ? ... ? n = k problem
此分類上一篇:[UVA][CutEdge] 796 - Critical Links

我要回應
是 (若未登入"個人新聞台帳號"則看不到回覆唷!)
* 請輸入識別碼:
請輸入以下數字 (ex:123)

(有*為必填)
詳全文