相框

一本通·提高篇 · 代码 · cpp · 难度 5/5 · 共 1298 字
并查集熔焊点求单环
一本通
练习
正文

// 原题：https://oj.yecheng.tv/p/T1533
// 题意：给定 n 个焊点、m 条导线（端点标 0 表示自由端），两种操作：烧熔焊点（分离其导线）、焊接两个自由端。求把全部导线改造成一个简单环（相框）的最少操作数。
// 思路：最终每个被用到的点度数恰为 2。统计：cnt2=度数>2 的点的个数（必须烧熔）；cnt1=奇度点个数（需两两配对焊接，花费 cnt1/2）。多个连通块时，每个无奇点的块需额外造 2 个奇点（不增加 cnt1 的焊接但可能多一次烧熔）。
// 复杂度：O(n+m) 时间 / O(n+m) 空间
// 易错点：端点标 0 时新建虚拟节点（编号递增，总点数可达 2m）；孤立点（度数 0）不计入连通块；答案 = cnt2 + cnt1/2。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200005;
int fa[MAXN];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int deg[MAXN];
bool flag1[MAXN], flag2[MAXN];
int main(){
    int n, m;
    if(!(cin>>n>>m)) return 0;
    for(int i=1;i<MAXN;i++) fa[i]=i;
    for(int i=0;i<m;i++){
        int x, y;
        cin>>x>>y;
        if(x==0) x=++n;
        if(y==0) y=++n;
        deg[x]++; deg[y]++;
        int fx=find(x), fy=find(y);
        if(fx!=fy) fa[fx]=fy;
    }
    int sum=0, cnt1=0, cnt2=0;
    for(int i=1;i<=n;i++){
        if(deg[i]==0) continue;
        if(find(i)==i) sum++;
        if(deg[i]&1){ cnt1++; flag1[find(i)]=1; }
        if(deg[i]>2){ cnt2++; flag2[find(i)]=1; }
    }
    if(sum>1){
        for(int i=1;i<=n;i++){
            if(deg[i] && find(i)==i && !flag1[i]){
                cnt1+=2;
                if(!flag2[i]) cnt2++;
            }
        }
    }
    cout<<cnt2+cnt1/2<<"\n";
    return 0;
}
相框

正文

一本通·提高篇的其它内容
