题解：P14625 [2018 KAIST RUN Fall] Electronic Circuit

syh110213 · 2025-11-29 07:14:23 · 题解

赛时看做的人不多，还以为会很难，结果自己做起来感觉还好，主要难在读题。

题意

给你一张 n 个节点 m 条边的图，判断这张图是不是一个正确的简单电路。

思路

我们思考如何简化电路：\ 对于一个并联电路，可以将其简化为一根导线，即：我们需要对边进行查重，所以可以用 set 维护。\ 对于以下两种情况：\ \ 注意到都可以简化为：\ \ 所以我们可以删除度数为 2 的点，重新连边，并用 set 去重，看最后能否简化为两个度数为 1 的点。

:::success[代码]

#include<bits/stdc++.h>
using namespace std;
int n,m,a,b,k,ans;
set<int> s[100005];
queue<int> q;
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i=0;i<m;i++){
        cin >> a >> b;
        s[a].insert(b);
        s[b].insert(a);
    }
    for(int i=1;i<=n;i++) if(s[i].size()==2) q.push(i);
    while(!q.empty()){
        int x=q.front();
        q.pop();
        if(s[x].size()!=2) continue;
        k=1;
        for(auto it:s[x]){
            if(k==1) a=it;
            if(k==2) b=it;
            k++;
        }
        s[x].erase(a);
        s[x].erase(b);
        s[a].erase(x);
        s[a].insert(b);
        s[b].erase(x);
        s[b].insert(a);
        if(s[a].size()==2) q.push(a);
        if(s[b].size()==2) q.push(b);
    }
    for(int i=1;i<=n;i++) if(s[i].size()==1) ans++;
    if(ans==2) cout << "Yes\n";
    else cout << "No\n";
    return 0;
}

:::