正文

hdu1829（种类并查集）

只有你  只有你  2022-08-29  426

关键词：

ps：本来是想找个二分图判断的题来写，结果百度到这鬼题

Problem Description

Background
Professor Hopper is researching the sexual behavior of a rare species of bugs. He assumes that they feature two different genders and that they only interact with bugs of the opposite gender. In his experiment, individual bugs and their interactions were easy to identify, because numbers were printed on their backs.

Problem
Given a list of bug interactions, decide whether the experiment supports his assumption of two genders with no homosexual bugs or if it contains some bug interactions that falsify it.

Input

The first line of the input contains the number of scenarios. Each scenario starts with one line giving the number of bugs (at least one, and up to 2000) and the number of interactions (up to 1000000) separated by a single space. In the following lines, each interaction is given in the form of two distinct bug numbers separated by a single space. Bugs are numbered consecutively starting from one.

Output

The output for every scenario is a line containing "Scenario #i:", where i is the number of the scenario starting at 1, followed by one line saying either "No suspicious bugs found!" if the experiment is consistent with his assumption about the bugs‘ sexual behavior, or "Suspicious bugs found!" if Professor Hopper‘s assumption is definitely wrong.

Sample Input

2 3 3 1 2 2 3 1 3 4 2 1 2 3 4

Sample Output

Scenario #1: Suspicious bugs found! Scenario #2: No suspicious bugs found!

思路：建立一个N*2的并查集，其中1~N表示公，N+1~2*N表示母，与poj食物链异曲同工。

#include<cstdio>

using namespace std;

#define max_n 2020*2

int par[max_n];

void init(int n)
{
    for(int i=1;i<=n;i++)
    {
        par[i]=i;
    }
}

int find(int x)
{
    if(par[x]==x) return x;
    else
    {
        return par[x]=find(par[x]);
    }
}

bool same(int x,int y)
{
return find(x)==find(y);
}

void unit(int x,int y)
{
    int fx=find(x);
    int fy=find(y);
    if(fx==fy) return ;
    par[fx]=fy;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int i=1;i<=t;i++)
    {
        int flag=0;
        int n,m;
        scanf("%d%d",&n,&m);
        init(n*2);

        for(int j=0;j<m;j++)
        {
            int x,y;
            scanf("%d%d",&x,&y);
            if(same(x,y)||same(x+n,y+n))
            {
                printf("Scenario #%d: Suspicious bugs found! ",i);
                flag=1;
                break;
            }
            else
            {
                unit(x,y+n);
                unit(x+n,y);
            }
        }

        if(flag==0)
        {
            printf("Scenario #%d: No suspicious bugs found! ",i);
        }
    }
    return 0;
}

hdu1829abug'slife(种类并查集)(代码片段)

传送门关键在于到根节点的距离，如果两个点到根节点的距离相等，那么他们性别肯定就一样（因为前面如果没有特殊情况，两个点就是一男一女的）。一旦遇到性别一样的，就说明找到了可疑的1#include<bits/stdc++.h>2usingnamesp... 查看详情

*hdu1829并查集

ABug‘sLifeTimeLimit:15000/5000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):14121 AcceptedSubmission(s):4603ProblemDescriptionBa 查看详情

hdoj1829abug'slife种类并查集(代码片段)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1829并查集的一个应用，就是检测是否存在矛盾，就是两个不该相交的集合有了交集。本题就是这样，一种虫子有两种性别，每次m次操作，每次给出(a,b)，如果a和b是同性别就出现了错误... 查看详情

hdu1829&poj2492abug'slife（推断二分图带权并查集）

ABug‘sLifeTimeLimit:15000/5000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):8528 AcceptedSubmission(s):2745ProblemDescriptionBac 查看详情

hdu3038howmanyanswersarewrong种类并查集

1#include<cstdio>2#include<cstring>3#include<algorithm>4usingnamespacestd;56intn,m;7constintmaxn=200005;8intfa[maxn];9intsum[maxn];1011intFind(intx){12if(x==fa[x])13returnx;14else{15 查看详情

hdu5285wyh2000andpupil(dfs或种类并查集)

wyh2000andpupilTimeLimit:3000/1500MS(Java/Others) MemoryLimit:131072/65536K(Java/Others)TotalSubmission(s):755 AcceptedSubmission(s):251ProblemDescription 查看详情

hdu1829abug'slife

...，问他们之间是否有可能存在同性恋的行为。思路：简单并查集，与食物链那题的思路比较像。每一次输入的两个数，定为a和b，每次将a和b+2000合并，将a+2000和b合并，表示他们是异性关系，一旦出现a和b同根，那么就是同性关系... 查看详情

并查集-解决区间和纠错问题hdu-3038

...间，如果区间左右界根节点不同就一定不存在矛盾（有点种类并查集的意思，形象来看就是存在冗余区间用于调整），然后可以通过现存集合推导出子节查看详情

种类并查集

　　一般的并查集是维护属于同一种类的元素，对于属于不同种类的元素之间的关系没有记录。种类并查集就是同一集合中的元素是已经确定关系的（是否属于同一种类），然后加一个group数组，记录一下孩子和父亲是否属于同... 查看详情

hdu5652indiaandchinaorigins并查集

IndiaandChinaOrigins ProblemDescriptionAlongtimeagotherearenohimalayasbetweenIndiaandChina,thebothculturesarefrequentlyexchangedandarekeptinsyncatthattime,buteventuallyhimalayasriseup.Withthatatf 查看详情

hdu3938并查集

求小于L的路径点对数（路上的最大值），按权值排序，从小到大并查集建图，有点kruskal的意思。/**@Date:2017-09-2217:30:11*@FileName:HDU3938并查集离线.cpp*@Platform:Windows*@Author:Lweleth([email protected])*@Link:https://github.com/*@Version:$Id$ 查看详情

hdu4641k-string后缀自动机并查集(代码片段)

...求出现次数桶排序（说是拓扑排序也可以？）就阔以了，种类就是t[i].len-t[t[i]. 查看详情

hdu3938(离线并查集)

...，有多少条路径（任意两点可到达的对数）题解：离线的并查集，刚开始的时候，暴力模拟，在每个并查集里边计算路径数目，果断T。。。正解：离线并查集，将每个查询保存起来，根查看详情

hdu1213howmanytables（并查集）

传送门DescriptionTodayisIgnatius‘birthday.Heinvitesalotoffriends.Nowit‘sdinnertime.Ignatiuswantstoknowhowmanytablesheneedsatleast.Youhavetonoticethatnotallthefriendsknoweachother,andallthefriendsdonotwan 查看详情

hdu1856并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1856 MoreisbetterTimeLimit:5000/1000MS(Java/Others) MemoryLimit:327680/102400K(Java/Others)TotalSubmission(s):29843 &nb 查看详情

*hdu3172并查集

VirtualFriendsTimeLimit:4000/2000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):8165 AcceptedSubmission(s):2345ProblemDescription 查看详情

hdu1325并查集

http://acm.hdu.edu.cn/showproblem.php?pid=1325 IsItATree?TimeLimit:2000/1000MS(Java/Others) MemoryLimit:65536/32768K(Java/Others)TotalSubmission(s):26387 & 查看详情

*hdu3047并查集

ZjnuStadiumTimeLimit:2000/1000MS(Java/Others) MemoryLimit:32768/32768K(Java/Others)TotalSubmission(s):3062 AcceptedSubmission(s):1182ProblemDescriptionIn1 查看详情

正文