一、题目描述
原题链接 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:
Output Specification:
Sample Input:
4 3 10 1 2 2 3 4 4 1 5 7 8 3 9 6 4 2 10 5 3 7
Sample Output:
2 10 Yes No
二、解题思路
并查集的题目，将题目每次给的两个数进行并操作，随后进行遍历统计，对输入的数进行寻找根结点，判断是否相等，对应输出即可。详情见代码注释。
三、AC代码
#include<iostream>
#include<cstdio>
#include<vector>
#include<set>
#include<algorithm>
using namespace std
;
const int maxn
= 10010;
int father
[maxn
];
int cnt
[maxn
] = {0};
bool vis
[maxn
] = {false};
int findFather(int x
)
{
int a
= x
;
while(x
!= father
[x
])
{
x
= father
[x
];
}
while(a
!= father
[a
])
{
int z
= a
;
a
= father
[a
];
father
[z
] = x
;
}
return x
;
}
void Union(int a
, int b
)
{
int faA
= findFather(a
);
int faB
= findFather(b
);
if(faA
!= faB
)
father
[faB
] = faA
;
}
int main()
{
int N
, K
, Q
, id
, tmp
;
for(int i
=0; i
<maxn
; i
++) father
[i
] = i
;
scanf("%d", &N
);
for(int i
=0; i
<N
; i
++)
{
scanf("%d%d", &K
, &id
);
vis
[id
] = true;
for(int j
=1; j
<K
; j
++)
{
scanf("%d", &tmp
);
Union(id
, tmp
);
vis
[tmp
] = true;
}
}
for(int i
=1; i
<maxn
; i
++)
{
if(vis
[i
])
{
int root
= findFather(i
);
cnt
[root
]++;
}
}
int trees
= 0, birds
= 0;
for(int i
=1; i
<maxn
; i
++)
{
if(vis
[i
] && cnt
[i
] != 0)
{
trees
++;
birds
+= cnt
[i
];
}
}
printf("%d %d\n", trees
, birds
);
scanf("%d", &Q
);
for(int i
=0; i
<Q
; i
++)
{
int a
, b
;
scanf("%d%d", &a
, &b
);
findFather(a
) == findFather(b
) ? printf("Yes\n") : printf("No\n");
}
return 0;
}
