pat甲級 1118 Birds in Forest (25 分)

1118 Birds in Forest (25 分)

DFS解法

#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
const int maxn = 10010;
struct bird
{
    int id;
    int root;  //同一顆樹上的根結點小鳥
} Bird[maxn];

int n, k, num = 0, treeNum = 0;
vector<int> Adj[maxn];
bool isVis[maxn];

void DFS(int v,int &root)
{
    Bird[v].root = root;
    isVis[v] = true;
    for (int i = 0; i < Adj[v].size();i++)
    {
        int u = Adj[v][i];
        if(isVis[u]==false)
        {
            DFS(u, root);
        }
    }
}

int main()
{
    memset(isVis, false, sizeof(isVis));
    scanf("%d", &n);
    int tNum, a, b;
    for (int i = 0; i < n;i++)
    {
        scanf("%d%d", &tNum,&a);
        if(a>num)
            num = a;
        for (int j = 1; j < tNum;j++)
        {
            scanf("%d", &b);
            if(b>num)
                num = b;
            Adj[a].push_back(b);
            Adj[b].push_back(a);
        }
    }
    for (int i = 1; i <= num;i++)
    {
        if(isVis[i]==false)
        {
            treeNum++;
            int root = i;   //就以一顆樹上第一個鳥i為根小鳥
            DFS(i, root);
        }
    }
    printf("%d %d\n", treeNum, num);
    scanf("%d", &k);
    for (int i = 0; i < k;i++)
    {
        scanf("%d%d", &a, &b);
        if(Bird[a].root!=Bird[b].root)
            printf("No\n");
        else
            printf("Yes\n");
    }
    return 0;
}