ABC292D并查集连通块遍历统计点数边数

#include <stdio.h>
#define N 200050
int n, m, i, j, k, x, y, a, b, h[N], v[N], u[N*2];
struct AB{
    int a, b, n;
} d[N*2];
void cun(int a, int b){
    d[++k].a = a, d[k].b = b;
    d[k].n = h[a], h[a] = k;
}
void dfs(int a){
    int i, b;
    v[a] = 1, x++;//点数
    for(int i=h[a]; i; i=d[i].n){
        b = d[i].b, y += u[i]^1;//边数
        u[i] = u[i^1] = 1;//不重复统计
        if(!v[b]) dfs(b);
    }
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=k=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        cun(a, b);
        cun(b, a);
    }
    for(i=1; i<=n; i++){
        if(!v[i]){
            x = y = 0;//统计每个连通块的点数、边数
            dfs(i);
            if(x != y) break;//个个都要点边相同
        }
    }
    printf("%s\n", i<=n?"No":"Yes");
    return 0;
}

并查集维护节点数、边数：

#include <stdio.h>
#define N 200050
int n, m, i, j, k, a, b, f[N], x[N], y[N];
int find(int x){
    if(x == f[x]) return x;
    return f[x] = find(f[x]);
}
int main(){
    scanf("%d%d", &n, &m);
    for(i=1; i<=n; i++){
        f[i] = i;
        x[i] = 1, y[i] = 0;
    }
    for(i=1; i<=m; i++){
        scanf("%d%d", &a, &b);
        a = find(a), b = find(b);
        if(a == b) y[a]++;
        else{
            f[a] = b;
            x[b] += x[a];//点数
            y[b] += y[a] + 1;//边数
        }
    }
    for(i=1; i<=n; i++){
        if(i == find(i)){
            if(x[i] != y[i]) break;
        }
    }
    printf("%s\n", i<=n?"No":"Yes");
    return 0;
}