Network Connections

Bob, who is a network administrator, supervises a network of computers. He is keeping a log connections between the computers in the network. Each connection is bi-directional. Two computers are interconnected if they are directly connected or if they are interconnected with the same computer. Occasionally, Bob has to decide, quickly, whether two given computers are connected, directly or indirectly, according to the log information.

Write a program which based on information input from a text file counts the number of successful and the number of unsuccessful answers to the questions of the kind :

is computer_i interconnected with computer_j ?

Input and Output 

The first line of the input contains the number of dataset, and it's followed by a blank line. Each dataset is defined as follows:

1.

The number of computers in the network (a strictly positive integer);

2.

A list of pairs of the form:

(a)

c computer_i computer_j, where computer_i and computer_j are integers from 1 to . A pair of this form shows that computer_i and computer_j get interconnected.

(b)

q computer_i computer_j, where computer_i and computer_j are integers from 1 to . A pair of this form stands for the question: is computer_i interconnected with computer_j?

There's a blank line between datasets.

Each pair is on a separate line. Pairs can appear in any order, regardless of their type. The log is updated after each pair of type (a) and each pair of type (b) is processed according to the current network configuration.

For example, the input file illustrated in the sample below corresponds to a network of 10 computers and 7 pairs. There are N1 successfully answered questions and N2 unsuccessfully answered questions. The program prints these two numbers to the standard output on the same line, in the order: successful answers, unsuccessful answers, as shown in the sample output. Print a blank line between datasets.

Sample Input 

1

10
c 1 5
c 2 7
q 7 1
c 3 9
q 9 6
c 2 5
q 7 5

Sample Input 

1,2

---

作法 : 併查集

#include<stdio.h>
int Parent[1001], Rank[1001];
void MakeInit(int n) {
    int i;
    for(i = 0; i <= n; i++)
        Parent[i] = i, Rank[i] = 1;
}
int FindParent(int x) {
    if(Parent[x] != x)
        Parent[x] = FindParent(Parent[x]);
    return Parent[x];
}
void Link(int x, int y) {
    if(Rank[x] > Rank[y]) {
        Rank[x] += Rank[y];
        Parent[y] = x;
    } else {
        Rank[y] += Rank[x];
        Parent[x] = y;
    }
}
void Union(int x, int y) {
    x = FindParent(x), y = FindParent(y);
    if(x != y)
        Link(x, y);
}
int CheckLink(int x, int y) {
    x = FindParent(x), y = FindParent(y);
    if(x != y)
        return 0;
    else
        return 1;
}
int main() {
    int T, N, x, y;
    char s[100], ss[2];
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &N);
        MakeInit(N);
        getchar();
        int yes = 0, no = 0;
        while(gets(s)) {
            if(s[0] == '\0')    break;
            sscanf(s, "%s %d %d", ss, &x, &y);
            if(ss[0] == 'c')
                Union(x, y);
            else {
                if(CheckLink(x, y))
                    yes++;
                else
                    no++;
            }
        }
        printf("%d,%d\n", yes, no);
        if(T)    puts("");
    }
    return 0;
}