티스토리 뷰

알고리즘 관련/BOJ

BOJ)14675 단절점과 단절선

JASON 자손9319 2017. 8. 6. 16:11

문제:icpc.me/14675


트리에서 단절선인지 단절점인지 여부를 판단하는 쿼리를 처리하는 문제이다.


단절선 단절점을 직접 구해줄 필요 없이, 트리이기 때문에 모든 선은 단절선이 된다.


트리에서 단절점 여부는 리프를 제외한 모든 노드는 단절점이 된다.


트리에서 리프판단 여부는 indegree의 개수를 세주면 된다.


1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
#include <cstdio>
#include <algorithm>
using namespace std;
int n, m, x, y, c[100010];
int main() {
    scanf("%d"&n);
    for (int i = 0; i < n - 1; i++) {
        scanf("%d%d"&x, &y);
        c[x]++, c[y]++;
    }
    scanf("%d"&m);
    while (m--) {
        scanf("%d%d"&x, &y);
        if (x == 1
            printf("%s\n", c[y] == "no" : "yes");
        else
            puts("yes");
    }
    return 0;
}
cs


'알고리즘 관련 > BOJ' 카테고리의 다른 글

BOJ)8462 배열의 힘  (0) 2017.08.15
BOJ)3172 현주와 윤주의 재미있는 단어 게임  (0) 2017.08.15
BOJ)14675 단절점과 단절선  (1) 2017.08.06
BOJ)14426 접두사 찾기  (0) 2017.08.04
BOJ)1938 통나무 옮기기  (0) 2017.08.03
BOJ)1445 일요일 아침의 데이트  (11) 2017.08.03
TAG
댓글
  • 프로필사진 감동받았다 충격적인 문제네.... 단절선 단절점 공부하다가 어떻게 두 개 다 합쳐보지 고민 중이었는데 아나 2020.03.25 00:56
댓글쓰기 폼