最小mex树

和撤销并查集一起来维护关系

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
const int N=1000010,M=100010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
int n,m; 
int p[N],sz[N],cnt;

stack<PII> S;
vector <PII> tr[4*M];
int find(int x){
    while(x!=p[x]) x = p[x];
    return p[x];
}
void merge(int a,int b){
    a = find(a), b = find(b);
    if (a == b) return ;
    if (sz[a] < sz[b]) swap (a,b);
    cnt++;
    sz[a] += sz[b];
    p[b] = a;
    S.push ({a,b});
}
void del(int pc){
    while (cnt>pc){
        auto [a,b] = S.top(); S.pop();
        sz[a] -= sz[b];
        p[b] = b;
        cnt--;
    }
}

void change(int u,int l,int r,int L,int R,PII t){
    if(L <= l and r <= R){
        tr[u].push_back(t);
        return;
    }
    int mid=(l+r)>>1;
    if(L<=mid) change(u<<1,l,mid,L,R,t);
    if(R>mid) change(u<<1|1,mid+1,r,L,R,t);
    return;
}

int ANS(int u,int l,int r){
    int pc = S.size();
    for(auto&[a,b]:tr[u]) merge(a,b);
    if (l == r){
        if (cnt == n-1) return l;
        del(pc);
        return 0;
    }
    int mid = l+r>>1;
    int ans;
    if(ans=ANS(u<<1,l,mid)) return ans;
    if(ans=ANS(u<<1|1,mid+1,r)) return ans;
    del(pc);
    return 0;
}


void solve(){

    cin>>n>>m;

    for(int i=1;i<=n;i++) p[i] = i, sz[i] = 1;

    while(m--){
        int a,b,w; cin>>a>>b>>w; w++;
        if(w!=1) change(1,1,M,1,w-1,{a,b});
        change(1,1,M,w+1,M,{a,b});
    }
    cout << ANS(1,1,M)-1 << endl;
}
signed main (){
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
         solve();
    }
}

二分图

撤销并查集和拓展域并查集

// 数学公式要变形
// 莫急莫急先读题
#include <bits/stdc++.h>
using namespace std;
#define lowbit(x) (x&(-x))
#define endl "\n"
#define ios ios::sync_with_stdio(0); cin.tie(0),cout.tie(0);
#define LF(x)   fixed<<setprecision(x)// c++ 保留小数
#define den(a) cout << #a << " = " << a << "\n";
#define deg(a) cout << #a << " = " << a << " ";
typedef long long LL;
typedef pair<int, int> PII;
typedef tuple<int,int,int> TUP;
const int N= 10101010,M=200010,INF=0x3f3f3f3f,mod=1e9+7;
const double pai=acos(-1.0);// pai
int n,m,k; 
int p[N],sz[N],cnt;

stack<PII> S;
vector <PII> tr[4*M];
int find(int x){
    while(x!=p[x]) x = p[x];
    return p[x];
}
void merge(int a,int b){
    a = find(a), b = find(b);
    if (a == b) return ;
    if (sz[a] < sz[b]) swap (a,b);
    cnt++;
    sz[a] += sz[b];
    p[b] = a;
    S.push ({a,b});
}
void del(int pc){
    while (cnt>pc){
        auto [a,b] = S.top(); S.pop();
        sz[a] -= sz[b];
        p[b] = b;
        cnt--;
    }
}

void change(int u,int l,int r,int L,int R,PII t){
    if(l > R or r <L) return ;
    if(L <= l and r <= R){
        tr[u].push_back(t);
        return;
    }
    int mid=(l+r)>>1;
    change(u<<1,l,mid,L,R,t);
    change(u<<1|1,mid+1,r,L,R,t);
    return;
}


void Solve(int u,int l,int r){

    bool ok = true;
    int pc = cnt;
    for(auto&[a,b]:tr[u]){
        int fa = find(a),fb = find(b);
        if(fa==fb){
            ok = false;
            for(int k=l;k<=r;k++) cout << "No" << endl;
            break;
        }
        merge(a,b+n);
        merge(b,a+n);
    }
    if(ok){
        if(l==r) cout << "Yes" << endl;
        else{
            int mid = l+r>>1;
            Solve(u<<1,l,mid),Solve(u<<1|1,mid+1,r);
        }
    }
    del(pc);
    return ;
}

void solve(){

    cin>>n>>m>>k;

    for(int i=1;i<=2*n;i++) p[i] = i,sz[i] = 1;

    while(m--){
        int x,y,l,r; cin>>x>>y>>l>>r; l++;
        change(1,1,k,l,r,{x,y});
    }
    Solve(1,1,k);
}
signed main (){
    ios// 不能有printf puts scanf
    int t=1;
    while(t--){
         solve();
    }
}