boj 14675 단절점과 단절선

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

 

단절점은 지웠을 때 그래프가 2개 이상으로 나눠지는 정점이라고 하고,

단절선은 지웠을 때 그래프가 2개 이상으로 나눠지는 간선이라고 합니다.

 

이 문제는 트리라고 명시되어 있기 때문에 애드혹으로 접근할 수 있습니다.

트리는 N - 1개의 간선만으로 N개의 정점을 연결하는 그래프입니다.

즉, 그래프에서 간선을 최소 갯수로 사용한게 트리입니다.

 

그렇다면 간선이 하나라도 없어진다면 더이상 하나의 그래프가 될 수 없습니다.

그러면 type == 2일 경우는 모두 yes를 출력하는걸로 마무리할 수 있습니다.

 

그 다음은 단절점인데

간선이 1개인 정점을 지우게 되더라도 여전히 하나의 그래프가 남게됩니다.

간선이 2개 이상인 정점을 지우게 되면 그 간선 만큼 2개 이상의 그래프로 나뉘는것을 알 수 있습니다.

 

그러면 정점을 지우면 해당 정점에 연결된 간선만큼 그래프가 나뉜다는 것을 알 수 있고,

type == 1일 경우는 해당 정점에 연결된 간선의 갯수만 세어준다면 쉽게 해결할 수 있습니다.

이는 그래프를 직접 벡터로 연결할 필요도 없이 각 정점에 연결된 간선의 갯수만 카운팅해주면 구할 수 있습니다.

 

 

#include <iostream>
#include <vector>
#define MAX 100001
using namespace std;
 
int cnt[MAX];
int N, M;
 
void func() {
    int type, x;
    while (M--) {
        cin >> type >> x;
        if (type == 1) {
            if (cnt[x] > 1) cout << "yes\n";
            else cout << "no\n";
        }
        else cout << "yes\n";
    }
}
 
void input() {
    int u, v;
    cin >> N;
    for (int i = 1; i < N; i++) {
        cin >> u >> v;
        cnt[u]++;
        cnt[v]++;
    }
    cin >> M;
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}