题目跳转

HDOJ6109

题目大意

给T组数据，要把这些数据分割成，合法+非法(1个)。
输出，分割的组数，和每组组内的数据组数

思路

并查集

并查集维护相同，用set来维护不同的边。

在合并的时候，采用启发式合并（数量小的加到数量大的中）
采用删边+增加边的操作，让不同的边连接两个集合的头。

不能使用加权并查集。
因为本题不是明确的一类一类，而是泛指的不同。

数据生成

#include <bits/stdc++.h>
#include <ctime>

using namespace std;

typedef long long LL;

int k, sum;
int a[30];

int random(int x)
{ // 获取 0~x-1 中间的一个随机数
  if (!x)
    return 0;
  return (LL)rand() * rand() % x;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  srand(time(0));
  cout << 5000 << endl;
  for (int T = 0; T < 5000; T++)
  {
    cout << random(100000) + 1 << ' ' << random(100000) + 1 << ' ' << random(2) << endl;
  }
  return 0;
}

CODE

#pragma GCC optimize(2)

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <set>

using namespace std;

typedef long long LL;

const int N = 1e5 + 10;

int cnt, maxv;
int fa[N], res[N];
bool flag;
set<int> edges[N];

void init()
{
  flag = false;
  for (int i = 1; i < N; i++)
    fa[i] = i;
  for (int i = 1; i <= maxv; i++)
    edges[i].clear();
  cnt++, maxv = -1;
}
int get_fa(int x)
{
  return fa[x] == x ? x : fa[x] = get_fa(fa[x]);
}
bool Union(int p, int q)
{
  if (p != q)
  {
    if (edges[p].size() > edges[q].size())
      swap(p, q);
    for (auto it : edges[p])
    {
      if (it == q)
        return false;
      edges[it].erase(p);
      edges[it].insert(q);
      edges[q].insert(it);
    }
  }
  fa[p] = q;
  return true;
}

int main()
{
  ios::sync_with_stdio(0);
  cin.tie(0);
  // freopen("i.txt", "r", stdin);
  // freopen("o.txt", "w", stdout);
  init();
  int T;
  cin >> T; // scanf("%d", &T);
  for (int CC = 1; CC <= T; CC++)
  {
    int x, y, op;
    cin >> x >> y >> op;
    maxv = max({maxv, x, y});
    int fx = get_fa(x), fy = get_fa(y);
    if (!op) // diff
    {
      if (fx == fy)
        res[cnt] = CC, flag = true;
      else
      {
        edges[fx].insert(fy);
        edges[fy].insert(fx);
      }
    }
    else if (!Union(fx, fy)) // same
      res[cnt] = CC, flag = true;
    if (flag)
      init();
  }
  cnt--;
  cout << cnt << endl;
  for (int i = 1; i <= cnt; i++)
    cout << res[i] - res[i - 1] << endl;
  return 0;
}
/*
  大概原理已经清楚了，因为不是一类一类的，不能用加权并查集。
  需要另外弄一个记录“不同”的边
  用set来改边，采用思想启发式合并（小合到大的里面去）
  set不能直接修改所以原本的pair<int,int> 方案 错误qwq
*/