사회망 서비스(SNS) 2553

BOJ 사회망 서비스(SNS) 2553

 

SOL)

 

트리의 끝점들인 leaf의 부모들은 early adaptor

이것을 재귀적으로 새롭게 갱신된 기존트리에서 다시

leaf를 선택

 

early adaptor를 고르는 과정에서

leaf와 연결된 부모노드를 2개를 삭제한다.

그리고 만약 이때까지 삭제한 간선의 수가 (2*(N-1))이면 종료

[-] Collapse

#include<cstdio>
#include<vector>
#include<set>
using namespace std;

vector<int> degree, early;
vector<set<int> > adj;
int N, Count = 0, ans = 0;
//간선삭제
bool eraseEdge(int u, int v){
    adj[v].erase(u);
    adj[u].erase(v);
    degree[v]--;
    degree[u]--;
    Count += 2;
}

int main(){
    scanf("%d", &N);
    degree = early = vector<int>(N);
    adj = vector<set<int> >(N);

    for (int i = 0; i < N - 1; i++){
        int u, v; scanf("%d%d", &u, &v);
        degree[u - 1]++;
        degree[v - 1]++;
        adj[u - 1].insert(v - 1);
        adj[v - 1].insert(u - 1);
    }

    vector<int> leaf;
    //초기 leaf 선택
    for (int i = 0; i < N; i++){
        if (degree[i] == 1){
            leaf.push_back(i);
        }
    }

    while (true){
        int l = leaf.size();
        vector<int> tmp;
        for (int i = 0; i < l; i++){
            int v = leaf[i]; //child
            int u = *adj[v].begin(); //parent
            eraseEdge(v, u); //간선삭제

            //만약 leaf의 부모가 아직 early dapotr가 아니면서 leaf가 early adaptor가 아니면
            if (!early[v] && !early[u]){
                ans++;
                early[u] = true;
            }
            if (Count == 2 * (N - 1)){
                printf("%d", ans);
                return 0;
            }

            if (degree[u] == 1){
                //만약 부모정점이 early adaptor이면 이와 여결된 할아버지? 간선을 삭제한다.
                if (early[u]){
                    int uu = *adj[u].begin();
                    eraseEdge(u, uu);
                    if (Count == 2 * (N - 1)){
                        printf("%d", ans);
                        return 0;
                    }
                    //할아버지 정점과 연결된 정점이 1개이면 할아버지는 leaf가 되므로 tmp에 추가
                    if (degree[uu] == 1)
                        tmp.push_back(uu);
                }
                //degree가 1이면서 방문이 안되었으므로 u는 새로운 leaf가 될수있음.
                else {

                    tmp.push_back(u);
                }
            }
        }
        leaf = tmp;
    }
}