PAT-A 真题 – 1118 Birds in Forest

Some scientists took pictures of thousands of birds in a forest. Assume that all the birds appear in the same picture belong to the same tree. You are supposed to help the scientists to count the maximum number of trees in the forest, and for any pair of birds, tell if they are on the same tree.

Input Specification:

Each input file contains one test case. For each case, the first line contains a positive number $N$ ( $\leq 1 0^{4}$ ) which is the number of pictures. Then $N$ lines follow, each describes a picture in the format:

$K$ $B^{1}$ $B^{2}$ ... $B^{K}$

where $K$ is the number of birds in this picture, and $B^{i}$ 's are the indices of birds. It is guaranteed that the birds in all the pictures are numbered continuously from 1 to some number that is no more than $1 0^{4}$ .

After the pictures there is a positive number $Q$ ( $\leq 1 0^{4}$ ) which is the number of queries. Then $Q$ lines follow, each contains the indices of two birds.

Output Specification:

For each test case, first output in a line the maximum possible number of trees and the number of birds. Then for each query, print in a line Yes if the two birds belong to the same tree, or No if not.

Sample Input:

Sample Output:

2 10
Yes
No

题目大意：第一行给定正整数n，接着给出n行数据，每行数据第一个是这一行有多少个数据，后面的为鸟的ID，这些ID对应的鸟在同一棵树上。然后输出总共有几棵树、几只鸟。接着给定查询数目m，然后给出m组ID，问这两个ID的鸟是否在同一棵树上。

对于有几只鸟，可以定义一个Exist数组，出现过的为1，没出现过的为0，统计1的个数即可。

这是一个并查集的问题，需要路径压缩。对于问有几棵树，只要路径压缩了，根节点就是负数，扫描所有节点找到根节点为负数并且在Exist数组中为1的节点就是树根，统计树根就求出了有多少棵树。

代码：

#include <iostream>
#include <algorithm>
#include <cstdio>
using namespace std;
const int maxn = 10010;
int S[maxn], Exist[maxn] = {0};
//并查集的查找 
int Find(int root){
  if(S[root] < 0) return root;
  //路径压缩 
  else return S[root] = Find(S[root]);
}
//并查集的归并 
void Union(int root, int child){
  root = Find(root), child = Find(child);
  if(root == child) return;
  //按秩归并 
  if(S[root] < S[child]){  //root集中的数量要多于child集中的数量 
    //child集依附在root集上
    S[root] += S[child];
    S[child] = root;
  }else{
    S[child] += S[root];
    S[root] = child;
  }
}

int GetBridNums(){
  int cnt = 0;
  for(int i = 1; i < maxn; i++)
    if(Exist[i]) cnt++;
  return cnt;
}

int GetTreeNums(){
  int cnt = 0;
  //cout << "S3和S4分别是：" << S[3] << ' ' << S[4] << endl;
  for(int i = 1; i < maxn; i++)
    if(S[i] < 0 && Exist[i]) cnt++;  //, cout << i << "是个根节点，里面有：" << -S[i] << endl;
  return cnt;
}

bool OnSameTree(int a, int b){
  a = Find(a), b = Find(b);
  if(S[a] == -1 && S[b] == -1) return false; 
  return S[a] == S[b];
}

int main(){
  int cnt;
  cin >> cnt;
  fill(S, S + maxn, -1);
  for(int i = 0; i < cnt; i++){
    int _cnt, root;
    cin >> _cnt >> root;
    Exist[root] = 1;
    for(int j = 1; j < _cnt; j++){
      int child;
      cin >> child;
      Union(root, child);
      Exist[child] = 1;
    }
  }
  cout << GetTreeNums() << ' ' << GetBridNums() << endl;
  cin >> cnt;
  for(int i = 0; i < cnt; i++){
    int id1, id2;
    cin >> id1 >> id2;
    if(OnSameTree(id1, id2))
      cout << "Yes" << endl;
    else cout << "No" << endl;
  }
  return 0;
}

斐斐のBlog