[BOJ] 24461 그래프의 줄기

https://www.acmicpc.net/problem/24461

24461번: 그래프의 줄기

문제

그래프에서 사이클이란, 한 정점에서 같은 정점까지, 반복되는 간선이 없으며, 길이가 0$0$이 아닌 경로이다.

사이클이 존재하지 않는 그래프가 주어진다.

우리는 이 그래프의 정점 중에서 연결된 간선이 하나인 정점을 가장자리 정점이라고 정의하자.

이 그래프의 가장자리 정점을 동시에 없애는 행동을 반복하면서, 그래프가 일직선의 모양이 되면 남아있는 정점의 집합을 그래프의 줄기라고 정의하자. 단, 가장자리 정점의 개수가 둘 이하라면 그래프가 일직선 모양이라고 한다.

위 그림과 같은 그래프가 있다고 할 때, 아래와 같이 가장자리 정점과 연결된 간선을 빨간색으로 표시하면 아래와 같다.

빨간색 간선과 연결된 가장자리 정점의 연결을 끊으면 아래 그림과 같이 일직선 모양으로 연결된 그래프의 줄기가 남는다. 만약 그래프가 일직선 모양이 되었다면, 가장자리 정점이 더 존재하더라도 더 이상 가장자리 정점들을 없애지 않는다.

이때 그래프의 줄기를 이루는 정점을 구하는 프로그램을 작성하시오.

입력

입력의 첫 번째 줄에는 처음 그래프의 정점의 수 N이 주어진다. (2≤N≤100000)

이후 N−1줄에 걸쳐 각 간선으로 연결된 두 정점의 번호 a,b가 입력된다. (0≤a, b<N, a≠b)

출력

 

출력의 첫 번째 줄에 그래프의 줄기를 이루는 정점의 번호들을 오름차순으로 정렬하고 공백으로 구분하여 출력한다.

 

---

풀이

SUAPC 대비로 연습셋에서 마주한 문제였는데 위상정렬을 제대로 알지 못해 틀린 문제이다.

솔직히 위상정렬을 알았어도 이 문제가 위상정렬이라는 것을 착안했을지는 잘 모르겠다.

 

위상정렬 알고리즘을 돌면서 가장자리 정점을 제거해주면 된다. 주의해야 할 점은 이 그래프는 양방향 그래프이므로 방문한 정점은 방문 표시를 해줘 재방문을 하지 않도록 처리해줘야 한다는 것이다.

---

코드

 

#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <climits>

#define SWAP(a, b, type) do { \
    type temp; \
    temp = a;  \
    a = b;     \
    b = temp;  \
} while (0)

#define INF 1000000000
#define endl '\n'
#define ll long long

using namespace std;

//정점에 연결된 간선의 갯수 저장
int cnt[100000];
//정점을 방문 했는지 안했는지 저장
bool visit[100000];
//트리 저장
vector<int> v[100000];
int N;


void input() {
    cin>>N;
    int to,from;
    for(int i=0;i<N-1;i++){
        cin>>from>>to;
        v[from].push_back(to);
        v[to].push_back(from);
        cnt[from]++;
        cnt[to]++;
    }
}

void init() {
}


void solution() {
    queue<int> q;
    for(int i=0;i<N;i++){
        if(cnt[i]==1){
            q.push(i);
            visit[i]=true;
        }
    }
    while(1){
        int size=q.size();
        //가장자리 정점이 두개일 때가 그래프줄기이다.
        if(size<=2) break;
        
        for(int i=0;i<size;i++){
            int start=q.front(); q.pop();
            cnt[start]--;
            for(int j=0;j<v[start].size();j++){
                int end=v[start][j];
                if(!visit[end]&&(--cnt[end]==1)){
                    visit[end]=true;
                    q.push(end);
                }
            }
        }
    }
    
    for(int i=0;i<N;i++){
        if(cnt[i]!=0) cout<<i<<" ";
    }
}

int main()
{
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    solution();
    return 0;
}