数据分割 HDU - 6109（并查集+set）

xi=xj">xi≠xj">xi=xj">xi≠xj">程序接受一些形如xi=xj 或 xi≠xj 的相等/不等约束条件作为输入，判定是否可以通过给每个 w 赋适当的值，来满足这些条件。
输入包含多组数据。
然而粗心的小w不幸地把每组数据之间的分隔符删掉了。
他只知道每组数据都是不可满足的，且若把每组数据的最后一个约束条件去掉，则该组数据是可满足的。

xi=xj">xi≠xj">xi=xj">xi≠xj">

xi=xj">xi≠xj">xi=xj">xi≠xj">思路：遍历一遍，如果xi!-yi,则用set集合保存不相等的关系，如果xi==yi,因为xi==yi,所以yi的不相等的集合，xi也不相等，合并xi和yi的集合。

#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 100005    
#define  ll unsigned long long
int a[maxn] = {};
int b[maxn] = {};
int e[maxn] = {};
int pre[maxn] = {};
int ans[maxn] = {};
int n, kx, ky, sum;
set<int>st[maxn];
void init()//初始化
{
    for (int i = 1; i < maxn; i++)
    {
        pre[i] = i;
        st[i].clear();
    }
}
int find(int root)//寻找根节点
{
    while (root != pre[root])
    {
        root = pre[root];
    }
    return root;
}
int main()
{
    sum = 1;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d%d%d", &a[i], &b[i], &e[i]);
    }
    init();
    for (int i = 1; i <= n; i++)
    {
        kx = find(a[i]);
        ky = find(b[i]);
        if (e[i] == 1)//相等关系
        {
            if (kx == ky)//确认相等
            {
                continue;
            }
            else if (st[kx].find(ky) != st[kx].end())//矛盾，在与kx不相等的集合中找到了ky
            {
                init();
                ans[sum] = i;
                sum++;
            }
            else
            {
                set<int>::iterator it;
                for (it = st[ky].begin(); it != st[ky].end(); it++)
                {
                    st[kx].insert(*it);//把ky的不相等集合并入kx集合
                    st[*it].erase(ky);
                    st[*it].insert(kx);
                }
                st[ky].clear();
                pre[ky] = kx;//修改
            }
        }
        else
        {
            if (kx == ky)//不相等关系，但kx==ky，矛盾
            {
                init();
                ans[sum] = i;
                sum++;
            }
            else//符合关系，添加进各自的集合
            {
                st[kx].insert(ky);
                st[ky].insert(kx);
            }
        }
    }
    printf("%d\n", sum - 1);
    for (int i = 1; i < sum; i++)
    {
        printf("%d\n", ans[i] - ans[i - 1]);
    }
}
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 多米诺骨牌

标签