[Acwing] 并查集 237. 程序自动分析

前言

一看上去 就是一道 很裸的题(还没有 食物链难呢 ) 结果大意了 给我做了半小时emm

思路

• 因为数据范围很大 用到的很小 所以我们想到hash (也就是离散化)
• 所以我们可以通过 类似于 邻接链表里面的(idx ++ 这种方法一样 处理)

(通过cnt标记 有多少个种类的数 然后我们find 的时候只需要 cnt的操作即可 没必要到1e9了)

unordered_map mp;
int get(int x)
{
    if(mp.count(x) == 0 ) mp[x] = ++cnt;
    return mp[x];
}

• 所以我们就可以 先 存放 (X = X) 的数组
• 然后我们在用(X!=X)的来判断即可

是不是非常简单呢 (QAQ)

CODE

#include 
#define IOS  ios::sync_with_stdio(false)
using namespace std;
const int N = 4e6+10;
int n,m,p[N],cnt;
unordered_map mp;
struct node
{
    int a,b,w;
} num[N];

int get(int x)
{
    if(mp.count(x) == 0 ) mp[x] = ++cnt;
    return mp[x];
}

int find(int x)
{
    if(x != p[x])
        return p[x] = find(p[x]);
    return p[x];
}

void solve()
{
    int n;
    cin>>n;
    for(int i=1; i>a>>b>>w;
        int fa = get(a);
        int fb = get(b);
        num[i] = {fa,fb,w};
    }

    for(int i=1; i