어흥
[백준 6416] 트리인가? (C++) 본문
728x90
반응형
문제 링크: https://www.acmicpc.net/problem/6416
1. 주의할 점
- 매 TC마다 Case를 1씩 증가시킨다
- 매 TC마다 벡터와 배열들을 초기화한다
- Root가 2개 이상 있는지, 없는지, 부모가 2개 이상인지, Root에서 모든 Node까지 도달 가능하지 전부 확인한다
- 0 0 또한 빈 트리로, 트리라고 출력해야 한다
2. 구현
- 입력받는 모든 Node들을 Set에 넣으며, 간선의 정보는 V[부모]에 자식에 대한 정보를 넣고, Conn[자식]++을 한다
- 마지막 입력으로 0 0 을 받았다면, Test() 함수를 수행하며 Root가 2개 이상 있는지, 없는지, 부모가 2개 이상인지 확인한다
- 위의 조건에서 위배되지 않았다면 Dfs(Root)를 수행하여 모든 Node들에 도달할 수 있는지 확인한다
#include <iostream>
#include <set>
#include <vector>
#include <queue>
using namespace std;
set<int> s;
vector<int> v[100001];
int conn[100001], visit[100001];
bool avail;
int root;
void dfs(int val) {
for (int i = 0; i < v[val].size(); i++) {
int next = v[val][i];
if (visit[next] > 0 || next == root) {
avail = false;
break;
}
visit[next] = 1;
dfs(next);
}
}
void test() {
for (auto it = s.begin(); it != s.end(); it++) {
int val = conn[*it];
if (val == 0) { //root인 경우
if (root == -1) root = *it;
else { //root가 2개 이상인 경우
avail = false;
break;
}
}
else if (val > 1) { //자식이며, 2가지 이상의 부모를 둔 경우
avail = false;
break;
}
}
if (root == -1) avail = false; //root가 없는 경우
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int t = 0, st, e;
while (1) {
t++;
cin >> st >> e;
if (st == -1 && e == -1) break;
else if (st == 0 && e == 0) {
cout << "Case " << t << " is a tree.\n";
continue;
}
//초기화
for (auto it = s.begin(); it != s.end(); it++) {
v[*it].clear();
conn[*it] = 0;
visit[*it] = 0;
}
s.clear();
avail = true;
root = -1;
s.insert(e);
s.insert(st);
v[st].push_back(e);
conn[e]++;
while (1) {
cin >> st >> e;
if (st == 0 && e == 0) break;
s.insert(st);
s.insert(e);
v[st].push_back(e);
conn[e]++;
}
test();
if (avail) {
dfs(root);
for (auto it = s.begin(); it != s.end(); it++) {
if (*it == root) continue;
if (visit[*it] > 1) {
avail = false;
break;
}
}
}
if (avail)
cout << "Case " << t << " is a tree.\n";
else
cout << "Case " << t << " is not a tree.\n";
}
return 0;
}
728x90
반응형
'알고리즘 > 백준' 카테고리의 다른 글
[백준 17780] 새로운 게임 (C++) (0) | 2020.06.18 |
---|---|
[백준 15681] 트리와 쿼리 (C++) (0) | 2020.06.15 |
[백준 5639] 이진 검색 트리 (C++) (0) | 2020.06.14 |
[백준 3671] 산업 스파이의 편지 (C++) (0) | 2020.06.12 |
[백준 3967] 매직 스타 (C++) (0) | 2020.06.12 |
Comments