1R/2016 09 20

오늘의 문제

• [1]

참가자

• 박인서

코드

15이원준

#include<iostream>
#include<vector>

using namespace std;

int paren[50001] = { 0, };
vector<vector<int>> vec(50001);

void sortParen(int parent){
  vector<int> tmp;
  for(int i = 0; i<vec[parent].size(); i++){
    if(!paren[(vec[parent])[i]]){
      tmp.push_back((vec[parent])[i]);
      paren[(vec[parent])[i]] = parent;
    }
  }
  for(int i = 0; i<tmp.size(); i++){
    sortParen(tmp[i]);
  }
}

int main(){
  int N;
  cin>>N;
  for(int i = 0; i<N-1; i++){
    int tmp1, tmp2;
    scanf("%d %d", &tmp1, &tmp2);
    vec[tmp1].push_back(tmp2);
    vec[tmp2].push_back(tmp1);
  }
  paren[1] = -1;
  sortParen(1);

  int M;
  cin>>M;
  for(int i = 0; i<M; i++){
    int m1, m2;
    vector<int> vec1;
    scanf("%d %d", &m1, &m2);
    while(m1 != -1){
      vec1.push_back(m1);
      m1 = paren[m1];
    }
    bool conti = true;
    while(m2 != -1 && conti){
      for(int i = 0; i<vec1.size(); i++){
        if(vec1[i] == m2){
          cout<<m2 <<endl;
          conti = false;
          break;
        }
      }
      m2 = paren[m2];
    }
  }
}

박인서

#include <cstdio>
#include <vector>
int a[50001] = { 0, }, d[50001];
std::vector<std::pair<int, int>> temp;

int find(int x, int y) {
	while (d[x]>d[y]) x = a[x];
	while (d[x]<d[y]) y = a[y];

	while (x != y)
	{
		x = a[x];
		y = a[y];
	}
	return x;
}

int main() {
	int n;
	scanf("%d", &n);
	a[1] = -1, d[1] = 0;
	for (int i = 1; i < n; i++) {
		int x, y;
		scanf("%d %d", &x, &y);
		if (a[x] == 0 && a[y] == 0)
			temp.push_back(std::pair<int, int>(x, y));
		else if (a[x] == 0) {
			a[x] = y;
			d[x] = d[y] + 1;
		}
		else {
			a[y] = x;
			d[y] = d[x] + 1;
		}
	}

	while (!temp.empty()) {
		for (int i = 0; i < temp.size(); i++) {
			int x = temp[i].first, y = temp[i].second;
			if (a[y] != 0) {
				a[x] = y;
				d[x] = d[y] + 1;
				temp.erase(temp.begin() + i);
				i--;
			}
			else if (a[x] != 0) {
				a[y] = x;
				d[y] = d[x] + 1;
				temp.erase(temp.begin() + i);
				i--;
			}
		}
	}

	int m;
	scanf("%d", &m);
	for (int i = 0; i < m; i++) {
		int t1, t2;
		scanf("%d %d", &t1, &t2);
		printf("%d\n", find(t1, t2));
	}
	return 0;
}

아이디어

15이원준

• 모든 노드를 저장한다.
• bfs로 1과 연결된 것부터 탐색하여 각 노드의 parent를 찾는다.
• m1의 부모들을 모두 저장하고 m2의 부모 노드들과 비교한다.
• 끝

박인서

• 일단 자신의 부모와 깊이를 저장을 해야됨.
  • 처음에 부모와 자식을 저장 할 수 없는 선들을 temp에 저장한 뒤 나중에 고려함.
• 그 뒤에 찾기는 일단 depth를 맞춘 뒤 한 단계씩 올라가면서 두 노드의 값을 비교함.