[swexpert] 1248. 공통조상 (C++, 트리, BFS, DFS)

풀이 참고

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;
}