a257. NCPC2011 Problem K Key Persons
內容 ：
Problem K
Key Persons
Input File: pk.in
Time Limit: 3 seconds
There is a secret club, named No-Communication-Permitted-Club (NCPC),
formed by n college students and every student has a unique ID which is a
positive integer. Two students can talk if and only if their ID have a common
factor bigger than 1. For convenience, we use the ID to represent the students.
Two students p and q are “relevant” if either they can talk or they can communicate
indirectly via other students. Otherwise they are “non-relevant”.
Hence, two students p and q are relevant if either p and q have a common
factor bigger than 1 or there is a sequence of integers (a1 = p, a2,…, ak = q)
in S such that ai and ai+1 for 1 ≦ i ≦ k-1 have a common factor bigger
than 1, where S is the setoff all ID of the students. The club needs to elect
some “key persons” to manage the club. A student x in S is a key person if
after excluding x from S, it can cause two relevant students p ∈S and q ∈S,
become non-relevant in S’ = S – x.
For example, consider S = (1,2,3,4,5,6,7,8,9). Then, 2 and 9 is relevant
because sequence (2,6,9) exists, where 2 and 6 have a common factor 2
(>1) and 6 and 9 have a common factor 3(>1). However, after excluding 6
from S, 2 and 9 becomes non-relevant in the resulting set S’ = S – 6 =
{1,2,3,4,5,6,7,8,9}. Hence, 6 is a key person.
Given a set club members S, your task is to write a computer program to conpute the number of key persons in S.
Technical Specification
All ID are integers at least one and at most 30000 and the number of
students in each test case is no more than 1000.
輸入說明 ：
The first line of the input file contains an integer, denoting the number if
test cases to follow. For each test case, the club S = {a1, a2, ... , an} is given
with the following format : The first line contains a positive integer n. In the
following n lines, each line represents one integer in S such that an integer in
the ith line represents ai .
輸出說明 ：
For each test case, output the number of key persons in S.
範例輸入 ：
282468101214161012345678910
範例輸出 ：
02
提示 ：
出處 ：
(以下代碼, 比賽中 AC, 並不代表是正確的, 讀者自行斟酌)
作法 : 關節點
時間一定是 O(n^2) 一定要建表(相鄰表), 用 DFS 將圖形建成一棵樹,
查找是否子節點可以回到父節點之上, 如果可以, 則是 Key person, 反之則不是,
另外, 一開始搜尋的節點(預設)要特別判斷
/**********************************************************************************/
/* Problem: a257 "NCPC2011 Problem K Key Persons" from NCPC2011 */
/* Language: C (1313 Bytes) */
/* Result: AC(688ms, 4.3MB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-16 21:07:55 */
/**********************************************************************************/
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define oo 2147483647
int map[1000][1000], Mt[1000];
int Used[1000], Time[1000], Ans;
int gcd(int x, int y) {
int tmp;
while(x%y) {
tmp = x, x = y, y = tmp%y;
}
return y;
}
int DFS(int T, int now, int start) {
int last = oo, i, tmp, flag = 0, ttry = 0;
Time[now] = T;
for(i = 0; i < Mt[now]; i++) {
if(Used[map[now][i]] == 0) {
Used[map[now][i]] = 1;
tmp = DFS(T+1, map[now][i], 0);
if(tmp >= T) flag = 1;
last = tmp < last ? tmp : last;
ttry++;
} else {
tmp = Time[map[now][i]];
last = tmp < last ? tmp : last;
}
}
if(start == 1) {
if(ttry > 1)
Ans++;
} else {
Ans += flag;
}
return last;
}
int main() {
int T, i, j, A[1001], n, tmp;
scanf("%d", &T);
while(T--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
memset(Mt, 0, sizeof(Mt));
memset(Used, 0, sizeof(Used));
memset(Time, 0, sizeof(Time));
Ans = 0;
for(i = 0; i < n; i++)
for(j = i+1; j < n; j++) {
tmp = gcd(A[i], A[j]);
if(tmp != 1) {
map[i][Mt[i]++] = j;
map[j][Mt[j]++] = i;
}
}
for(i = 0; i < n; i++)
if(Used[i] == 0) {
Used[i] = 1, Time[i] = 1;
DFS(1, i, 1);
}
printf("%d\n", Ans);
}
return 0;
}