백준16183 Electronic Circuit

작성일 | In

문제 링크

  • https://icpc.me/16183

사용 알고리즘

  • 트리 디컴포지션

시간복잡도

  • $O(N+M)$

풀이

주어진 그래프가 Series-Parallel Graph인지 판별하는 문제입니다. 그래프의 treewidth가 2 이하인지 판별하는 문제라고 볼 수도 있습니다.

그래프를 생성하는 과정을 거꾸로 생각하면, 아래 두 가지 연산을 적용해서 그래프를 간선 하나로 축소시킬 수 있는지 판별하는 문제가 됩니다.

  • 평행한 두 간선을 하나의 간선으로 병합 (parallel 연결의 역연산)
  • 차수가 2인 정점을 제거해서 두 간선을 하나로 병합 (series 연결의 역연산)

인접 리스트를 std::set 등으로 관리하면 첫 번째 연산을 효율적으로 수행할 수 있습니다.
두 번째 연산은 재귀적으로 수행할 수 있습니다. 차수가 2인 정점을 선택해서 간선을 병합한 뒤, 병합된 간선의 양 끝점 중 차수가 2인 간선이 있다면 재귀적으로 작업을 수행하면 됩니다.

두 가지 연산만 이용해 정점을 2개만 남기고 모두 없앨 수 있다면 주어진 그래프는 series-parallel graph입니다.
std::set을 사용하면 $O(M \log N)$, std::unordered_set을 사용하면 $O(N+M)$입니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <bits/stdc++.h>
using namespace std;

int N, M, Del[101010];
set<int> G[101010];

void Go(int v){
    if(G[v].size() != 2) return;
    Del[v] = 1;
    int x = *G[v].begin(), y = *G[v].rbegin();
    G[v].erase(x); G[x].erase(v); G[x].insert(y);
    G[v].erase(y); G[y].erase(v); G[y].insert(x);
    Go(x); Go(y);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> N >> M;
    for(int i=1,s,e; i<=M; i++) cin >> s >> e, G[s].insert(e), G[e].insert(s);
    for(int i=1; i<=N; i++) Go(i);
    if(count(Del+1, Del+N+1, 0) == 2) cout << "Yes";
    else cout << "No";
}