A Bug's Life（带权并查集）POJ - 2492

Bug有两种性别，异性之间才交往， 让你根据数据判断是否存在同性恋，输入有 t 组数据,每组数据给出bug数量n, 和关系数m, 以下m行给出相交往的一对Bug编号 a, b。只需要判断有没有，按题目要求输出。

思路：我们开一个两倍的数组，存上对应的关系。

例如：有n个bug，其中（2， 3）,（3,4）,(2,4)是交往关系

记为(2,3+n),(2+n,3)为两对。

(3,4+n),(3+n,4)为两对。

因为（3+n,4)和(2,3+n)都为交往关系

所以2,4都指向3+n;所以2和4同性。

而2,4又是交往的。

所以是同性恋

#define _CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
#include
#include<set>
#include 
#include
#include    
#include
#include
#include
using namespace std;
#define inf 1<<30
#define eps 1e-7
#define LD long double
#define LL long long
#define maxn 100000005    
int pre[100009] = {};
int rootsearch(int root)
{
    int son;
    son = root;
    while (root != pre[root])//这个数不是领导，继续往下找
    {
        root = pre[root];
    }
    while (son != root)//路径压缩，把找到的下级数全部指向最高领导
    {
        int temp = pre[son];
        pre[son] = root;
        son = temp;
    }
    return root;//返回最高领导
}
int main()
{
    int T, Case = 1;
    scanf("%d", &T);
    while (T--)
    {
        memset(pre, 0, sizeof(pre));
        int n, m;
        int a, b, flag = 0;
        scanf("%d%d", &n, &m);
        for (int i = 1; i <= 2*n; i++)
        {
            pre[i] = i;
        }
        for (int i = 1; i <= m; i++)
        {
            scanf("%d%d", &a, &b);
            if (rootsearch(a) == rootsearch(b) || rootsearch(a + n) == rootsearch(b + n))//检查是否是同性恋
            {
                flag = 1;
            }
            else
            {
                pre[rootsearch(a)] = pre[rootsearch(b + n)];//a和b+n交往
                pre[rootsearch(b)] = pre[rootsearch(a + n)];//b和a+n交往
            }
        }
        printf("Scenario #%d:\n", Case++);
        if (flag)
            printf("Suspicious bugs found!\n");
        else
            printf("No suspicious bugs found!\n");
        if (T != 0)
            printf("\n");
    }
}
ACM

相关

acm讲解

「acmhdu - 6314」Matrix

第十三届河南省ACM-ICPC游记

ACM模板

Hyperf 接入阿里云ACM应用配置管理中心

[ACM] BFS & 双端BFS & A* & 双边BFS

计算几何 / Geometry（ACM-Template 2.0）

ACM入门方式

Linux 下使用 acme.sh 配置 Let's Encrypt 免费 SSL 证书 + 通配符证书

如何写好一篇高质量的IEEE/ACM Transaction级别的计算机科学论文?

ACM- java在acm中的快速读入，多组读入，快速输出模板

ACM - 动态规划 - P1282 多米诺骨牌

标签