1118 Birds in Forest (25 分)

摘要:
=y){p[x]=y;}返回;}boolistrue(inta,intb){returnfound(a)==found(b);}intmain(){intx,y;set<int>s;for(inti=1;i<=10010;i++){p[i]=i;}scanf(“%d”,&n);对于(inti=1;i˂=n;i++){scanf(“%d”,&m);对于(intj=1;j˂=m;j++){scanf(”%d“,&a[j]);s.insert(a[j]]);}对于(intj=2;j˂=m;j++){联合(a[j-1],a[j]]);}}intsum=s.size();set<int>ss;对于(inti=1;i˂=sum;i++){ss.insert(找到(i));}cout˂˂ss.size()˂˂“”˂˂sum˂˂endl;扫描(“%d”,&k);而(k--){scanf(“%d%d”,&x,&y);if(istrue(x,y)){cout˂˂“是”˂˂endl;}否则{cout˂˂“否”˂˂end l;}}返回0;}

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 (104​​) which is the number of pictures. Then N lines follow, each describes a picture in the format:

B1​​ B2​​ ... BK​​

where K is the number of birds in this picture, and Bi​​'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 104​​.

After the pictures there is a positive number Q (104​​) 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:

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
 
#include <bits/stdc++.h>
using namespace std;
int p[10010];
int visit[10010];
int a[10010];
int n,m,k;
int found(int a)
{
    if(a==p[a]){
        return a;
    }
    return p[a]=found(p[a]);
}
void unite(int a,int b)
{
    int x = found(a);
    int y = found(b);
    if(x!=y){
        p[x] = y;
    }
    return ;
}
bool istrue(int a,int b){
    return found(a) == found(b);
}
int main()
{
    int x,y;
    set<int> s;

    for(int i=1;i<=10010;i++){
        p[i] = i;
    }
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&m);
        for(int j=1;j<=m;j++)
        {
            scanf("%d",&a[j]);
            s.insert(a[j]);
        }
        for(int j=2;j<=m;j++)
        {
            unite(a[j-1],a[j]);
        }
    }
    int sum = s.size();
    set<int> ss;
    for(int i=1;i<=sum;i++)
    {
        ss.insert(found(i));
    }
    cout<<ss.size()<<" "<<sum<<endl;
    scanf("%d",&k);
    while(k--)
    {
        scanf("%d%d",&x,&y);
        if(istrue(x,y)){
            cout<<"Yes"<<endl;
        }else{
            cout<<"No"<<endl;
        }
    }
    return 0;
}

免责声明:文章转载自《1118 Birds in Forest (25 分)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇ACM-ICPC 2018 焦作赛区网络预赛 A Magic Mirror(签到)1107 Social Clusters (30 分)下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

HDU5783

HDU 5783 题意: 给出字符串 A 和 它的长度, 要求把 A 分成尽可能多的连续字串, 且每一段的每个前缀和都 >= 0 ; 答案保证存在。 解题:因为要求每一段的每个前缀和都大于等于 0 ,答案一定存在,所以就直接从后往前找,遇到一段满足条件的就算上,否则继续往前加,和用64位整数存(WA*1 )= =。 #include<bits/...

分块

其实就是把讲课的课件整理一下 算是对于分块的详解(?)了吧 首先,我们来考虑这样一个模型:有一段连续的老板的垃圾桶塞人序列a[1]~a[n],然后现在我们需要执行几类操作: 1.求出其中一段垃圾桶内人数的和 鸭我会!前缀和! 2.区间垃圾桶里塞人 Emmmm线段树!树状数组! 3.查询一段区间上有多少个垃圾桶里人数<k (k>0...

HDU-2602-Bone Collector

题目链接 http://acm.hdu.edu.cn/showproblem.php?pid=2602 题意 t n v //n代表数量,v 代表背包的体积 v1 v2......vn//价值 m1 m2 ...... mn// 体积 求最大的价值 01背包裸题 代码 #include<stdio.h>#include<string.h&...

UVA 1482 Playing With Stones

(蓝书里有这个题貌似) 一言不合就打表,可以发现sg数组是个分形的,所以可以推出递推式: 1.x是偶数时,sg(x)=x/2 2.否则,sg(x)=sg(x/2) #include<iostream>#include<cstdio>#include<cstdlib>#include<algorithm>...

函数,拷贝(开了个玩笑,设了个张浩东)

#include<stdio.h>int n;void zhd(double a[10000]){scanf("%d",&n);for(int i=0;i<=n-1;i++){scanf("%lf",&a[i]);}}int main(){double b[10000];zhd(b);for(int i=0;i<=n-...

最新文章