题解

unusual flower⁧

2025-11-29 13:38:25

发布于：上海

30阅读

0回复

0点赞

时间刺客

#include<bits/stdc++.h>
using namespace std;
const int MAX_SIZE = 3 * 50000 + 10;
// parent[i]：并查集父节点
vector<int> parent(MAX_SIZE);
// rank_：并查集按秩合并使用
vector<int> rank_(MAX_SIZE, 0);
// 并查集查找（带路径压缩）
int find(int x){
    if(parent[x] != x){
        parent[x] = find(parent[x]);
    }
    return parent[x];
}
// 并查集合并
void unite(int x, int y){
    x = find(x);
    y = find(y);
    if(x == y) return;

    if(rank_[x] < rank_[y]) parent[x] = y;
    else{
        parent[y] = x;
        if(rank_[x] == rank_[y]) rank_[x]++;
    }
}
// 初始化并查集
void init(int size){
    for(int i = 1; i <= size; ++i){
        parent[i] = i;
        rank_[i] = 0;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n, k;
    cin >> n >> k;
    // 开 3*n 大小空间
    init(3 * n);
    int sum = 0; // 假话数量
    for(int i = 0; i < k; ++i){
        int d, x, y;
        cin >> d >> x >> y;
        // 越界是假话
        if(x > n || y > n){
            sum++;
            continue;
        }
        // 2 X X（自己吃自己）是假话
        if(d == 2 && x == y){
            sum++;
            continue;
        }
        if(d == 1){ // x 和 y 同类
            // 若 x 与 y+n 或 y 与 x+n 属于同一集合，则矛盾
            if(find(x) == find(y+n) || find(y) == find(x+n)){
                sum++;
            }
            else{
                // 合并三类关系
                unite(x, y);
                unite(x+n, y+n);
                unite(x+2*n, y+2*n);
            }
        }
        else{ // d == 2: x 吃 y
            // 若 x 与 y 同类 或 y 吃 x（y 与 x+n 同属一类）则矛盾
            if(find(x) == find(y) || find(y) == find(x+n)){
                sum++;
            }
            else{
                unite(x, y+n);
                unite(x+n, y+2*n);
                unite(x+2*n, y);
            }
        }
    }
    cout << sum << endl;
    return 0;
}

有帮助，赞一个

去预览

0/2000

全部评论 1

182

#include<bits/stdc++.h>
#include <fstream>
#define cout std::cout
#define cin std::cin
#define sort std::sort
#define ifstream std::ifstream
#define vector std::vector
#define ll long long
#define inf 0x3f3f3f3f3f3f3f3f
int fa[222222];
int find(int x){if(fa[x]==x)return x;else return fa[x]=find(fa[x]);}
void ma(int x,int z){fa[find(x)]=find(z);}
void ad(int x){int i=0;while(++i<=x)fa[i]=i;}
int main(){
    int n,m,cnt=0;
    cin>>n>>m;
    ad(n*3);
    while(m--){
        int x,y,z;
        cin>>z>>x>>y;
        if((y>n||x>n)||(y==x&&z==2))cnt++;
        else if(z==1){
            //x=>x`=>x``=>x
            if(find(x)==find(y+n)|find(x+n)==find(y)){
                cnt++;
                continue;
            }
            ma(x,y);
            ma(x+n,y+n);
            ma(x+n*2,y+n*2);
        }else {
            //x=>x`=>x``=>x
            if(find(x)==find(y)||find(x)==find(y+n)){
                cnt++;
                continue;
            }
            ma(x,y+n*2);
            ma(x+n,y);
            ma(x+n*2,y+n);
        }
    }cout<<cnt;
}

2026-09-19 来自浙江

郭智铭

182

#include<bits/stdc++.h>
using namespace std ;
#define int long long
#define pll pair<long long , long long>
const long long Inf = 0x3f3f3f3f ;
const long long mod = 1e9 + 7 ;
int n , k , fa[1000010] , cnt ;
int find (int x){
    if(fa[x] == x)return x ;
    else {
        return fa[x] = find(fa[x]) ;
    }
}
void merge (int x , int y){
    int x1 = find(x) ;
    int y1 = find(y) ;
    fa[x1] = y1 ;
    return ;
}
signed main(){
    // freopen(".in" , "r" , stdin) ;
    // freopen(".out" , "w" , stdout) ;
    // --------------------------------------------------
    ios::sync_with_stdio(false) ;
    cin.tie(nullptr) ;
    cout.tie(nullptr) ;
    cin >> n >> k ;
    for(int i = 1 ; i <= 3 * n ; i ++){
        fa[i] = i ;
    }
    for(int i = 1 ; i <= k ; i ++){
        int u , x , y ;
        cin >> u >> x >> y ;
        if(x > n || y > n)cnt ++ ;
        else if(u == 1){
            if(find(x) == find(y + n) || find(y) == find(x + n))cnt ++ ;
            else {
                merge(x , y) ;
                merge(x + n , y + n) ;
                merge(x + 2 * n , y + 2 * n) ;
            }
        } else {
            if(find(x) == find(y) || find(y) == find(x + 2 * n))cnt ++ ;
            else {
                merge(x + n , y) ;
                merge(x + 2 * n , y + n) ;
                merge(x , y + 2 * n) ;
            }
        }
    }
    cout << cnt << endl ;
    // --------------------------------------------------
    // fclose(stdin) ;
    // fclose(stdout) ;
    return 0 ;
}

欣赏一下

2026-09-25 来自浙江