[swexpert] 1248. 공통조상 (C++, 트리, BFS, DFS)
728x90
반응형
풀이 참고
https://yabmoons.tistory.com/319
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <queue>
#include <cstring>
#define endl "\n"
#define MAX_N 10001
using namespace std;
typedef struct st {
int num;
int parent;
int child[2];
int index;//몇 번째 자식인지 판별
}Node;
int v, e, a,b, ancestor, subsize;
int dist[MAX_N][2];
Node tree[MAX_N];
void init() {
memset(dist, 0, sizeof(dist));
for (int i = 0; i < MAX_N; i++) {
tree[i].num = i;
tree[i].index = 0;
tree[i].parent = tree[i].child[0] = tree[i].child[1] = 0;
}
}
void input() {
cin >> v >> e >> a >> b;
for (register int i = 0; i < e; i++) {
int p, c; // 1~v까지
cin >> p >> c;
tree[p].child[tree[p].index++] = c;
tree[c].parent = p;
}
}
void dfs(int num, int cnt, int idx) {
dist[num][idx] = cnt;
if (tree[num].parent != 0) {
dfs(tree[num].parent, cnt + 1, idx);
}
}
int bfs(int start) {
queue<int> q;
q.push(start);
int cnt = 1;
while (!q.empty()) {
int cur = q.front();
//cout << cur << endl;
q.pop();
for (int i = 0; i < 2; i++) {
if (tree[cur].child[i] != 0) {
//cout << tree[cur].child[i] << endl;
q.push(tree[cur].child[i]);
cnt++;
}
}
}
return cnt;
}
void solution() {
dfs(a, 0, 0);
dfs(b, 0, 1);
int maxa=-1,maxb=-1;
for (int i = 1; i <= v; i++) {
if (dist[i][0] != 0 && dist[i][1] != 0) {
if (maxa == -1 || maxa > dist[i][0]) {
if (maxb == -1 || maxb > dist[i][1]) {
maxa = dist[i][0];
maxb = dist[i][1];
ancestor = i;
}
}
}
}
subsize = bfs(ancestor);
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
for (int tc = 1; tc <= t; tc++) {
init();
input();
solution();
cout << "#" << tc << " " << ancestor << " " << subsize << endl;
}
return 0;
}
728x90
반응형
'swexpert' 카테고리의 다른 글
[swexpert] 7510. 상원이의 연속합 (c++, 누적합) (0) | 2021.10.18 |
---|---|
[SWEA] 2948. 문자열 교집합 (C++, 해시) (0) | 2021.10.06 |
[SWEA] 1256. K번째 접미어 (C++) (0) | 2021.10.06 |
[swexpert] 1230. 암호문3 (C++, 연결리스트) (0) | 2021.10.05 |
[SWEXPERT] 1232. 사칙연산 (이진트리, C++, D4) (0) | 2021.10.01 |
TAGS.