1248. [S/W 문제해결 응용] 3일차 - 공통조상

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD&categoryId=AV15PTkqAPYCFAYD&categoryType=CODE

SW Expert Academy

 

부모 자식 관계를 저장하는 트리를 따로 만들어서 추적하면서 공통 조상만 따로 저장 

거리순으로 정렬 후 가장 가까운 공통조상 뽑고 반대방향으로 큐로 탐색하면서 서브트리 크기 구하면 끝.

 

#include<iostream>
#include<vector>
#include<string.h>
#include<queue>
#include<algorithm>
using namespace std;

int V, E;
vector<int> vec[10001];
vector<int> vec2[10001];
int visit[10001];

int A, B;


int main(int argc, char** argv)
{
	int test_case;
	int T;

	cin >> T;
	/*
	   여러 개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
	*/
	for (test_case = 1; test_case <= T; ++test_case)
	{

		cin >> V >> E >> A >> B;
		memset(visit, 0, sizeof(visit));
  


		for (int i = 1; i <= V; i++)
		{
			vec[i].clear();
            vec2[i].clear();
		}

		int father, son;
		for (int i = 0; i < E; i++)
		{
			cin >> father >> son;
			vec[son].push_back(father);
			vec2[father].push_back(son);
		}

		queue<pair<int,int> > que;
		for (int i = 0; i < vec[A].size(); i++)
		{
			que.push({ 1,vec[A][i] });
		}

		while (!que.empty())
		{
			int distance = que.front().first;
			int next = que.front().second;

			visit[next] = distance;
			que.pop();

			for (int i = 0; i < vec[next].size(); i++)
			{
				que.push({ distance + 1,vec[next][i] });
			}

		}

		queue<pair<int, int> > que2;
		for (int i = 0; i < vec[B].size(); i++)
		{
			que2.push({ 1,vec[B][i] });
		}

		vector<pair<int, int> > answer;

		while (!que2.empty())
		{
			int distance = que2.front().first;
			int next = que2.front().second;
			que2.pop();

			if (visit[next])
			{
				if (visit[next] > distance)
				{
					answer.push_back({ distance,next });
				}
				else
				{
					answer.push_back({ visit[next],next });
				}
			}
			

			for (int i = 0; i < vec[next].size(); i++)
			{
				que2.push({ distance + 1,vec[next][i] });
			}

		}

		sort(answer.begin(), answer.end());

		int count = 1;
		queue<int> result;

		for (int i = 0; i < vec2[answer[0].second].size(); i++)
		{
			result.push(vec2[answer[0].second][i]);
			count++;
		}

		while (!result.empty())
		{
			int next = result.front();
			result.pop();

			for (int i = 0; i < vec2[next].size(); i++)
			{
				result.push(vec2[next][i]);
				count++;
			}
		}

		cout << "#" << test_case << " " << answer[0].second << " " << count << endl;
	}
	return 0;//정상종료시 반드시 0을 리턴해야합니다.
}