[1248번] 공통조상

문제 출처 :

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD

알고리즘 분석 :

문제 해결에 필요한 사항

1. BFS

2. LCA

이 문제는 2가지 방법으로 해결 가능하다.

도착지점 두개를 큐에 집어넣고 BFS를 돌려 이미 visit한곳에 다른 정점에서 오는 것이 visit를 하게 된다면

그것이 가장 가까운 공통 조상이 된다.

그 외에는 LCA 알고리즘을 이용하면 문제해결을 할 수 있다.

소스 코드 : 

<< LCA 알고리즘이 없이 해결 >> 

 

/*
    https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD
    이 문제는 사실 lca 알고리즘을 이용하지 않아도 된다.
    그 이유는 lca에서 dp를 이용하는데 
    여러 쿼리가 계속 들어올 때 빠르게 해결하기 위해 전처리를 하는 것이고
    현재 문제에서는 한번만 답을 내면 되기 때문에
    visit배열을 이용하여 해결 할 수 있다.
    최소 공통 조상을 찾기위한 노드 a,b를 queue에 push하고 
    찾아가다가 visit를 방문한 곳에 한번 더 방문하려한다면 그곳이 최소 공통 조상이다.
*/
#include <iostream>
 
#define swap(a,b){int t = a; a = b; b = t;}
#define MAX_NODE 10002
 
int visit[MAX_NODE];
int visitCnt;
int queue[MAX_NODE];
int first, last;
 
class _vector {
public:
    int sz;
    int capacity;
    int *vc;
    _vector() {
        capacity = 8;
        sz = 0;
        vc = new int[capacity];
    }
    ~_vector() {
        delete[] vc;
    }
 
    void push_back(int val) {
        if (sz == capacity) {
            int *tmp = new int[capacity];
            for (int i = 0; i < capacity; i++)
                tmp[i] = vc[i];
            
            capacity *= 2;
 
            delete[] vc;
            vc = new int[capacity];
 
            for (int i = 0; i < capacity; i++)
                vc[i] = tmp[i];
        }
        vc[sz++] = val;
    }
 
    void clear() {
        capacity = 8;
        sz = 0;
 
        delete[] vc;
 
        vc = new int[capacity];
    }
 
    int size() {
        return sz;
    }
    bool empty() {
        return sz ? false : true;
    }
 
    int &operator [](int i) {
        return vc[i];
    }
};
 
void init() {
    visitCnt++;
    first = last = 0;
}
int main()
{
    freopen("input.txt", "r", stdin);
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        init();
        _vector ctop[MAX_NODE]; // 부모에서 자식 간선
        _vector ptoc[MAX_NODE]; // 자식에서 부모 간선
 
        int v, e, a, b;
        scanf("%d %d %d %d", &v, &e, &a, &b);
 
        for (int i = 0; i < e; i++) {
            int par, child;
            scanf("%d %d", &par, &child);
 
            ctop[par].push_back(child);
            ptoc[child].push_back(par);
        }
 
        int lca = -1;
 
        queue[last++] = a;
        queue[last++] = b;
 
        while (first < last) {
            int here = queue[first++];
            if (visit[here] == visitCnt) {
                lca = here;
                break;
            }
            visit[here] = visitCnt;
            for (int i = 0; i < ptoc[here].size(); i++) {
                int next = ptoc[here][i];
                queue[last++] = next;
            }
        }
        
        int cnt = 0;
        first = last = 0;
        queue[last++] = lca;
 
        while (first < last) {
            int here = queue[first++];
            cnt++;
            for (int i = 0; i < ctop[here].size(); i++) {
                int next = ctop[here][i];
                queue[last++] = next;
            }
        }
        printf("#%d %d %d\n", tc, lca, cnt);
    }
    
 
    return 0;
}
 

<< LCA 알고리즘 이용 >> 

/*
  https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV15PTkqAPYCFAYD
    https://www.crocus.co.kr/660
    lca 알고리즘을 이용하면 최소 공통 조상을 찾을 수 있다.
    이때 해당하는 lca에서 나오는 subtree의 노드수는
    vc벡터를 하나 더 만들어 bfs로 해결한다.
*/
 
#include <iostream>
#include <cstdio>
#include <vector>
#include <cmath>
#include <queue>
 
#define swap(a,b){int t = a; a = b; b = t;}
#define MAX_NODE 50002
 
using namespace std;
 
int depth[MAX_NODE];
int ac[MAX_NODE][20];
 
typedef pair<int, int> pii;
vector<int> graph[MAX_NODE];
vector<int> vc[MAX_NODE];
int max_level;
 
void init() {
    for (int i = 0; i < MAX_NODE; i++)
        vc[i].clear(), graph[i].clear();
}
 
void getTree(int here, int parent)
{
    depth[here] = depth[parent] + 1;
 
    ac[here][0] = parent;
 
    max_level = (int)floor(log2(MAX_NODE));
 
    for (int i = 1; i <= max_level; i++)
    {
        int tmp = ac[here][i - 1];
        ac[here][i] = ac[tmp][i - 1];
    }
 
    int len = graph[here].size();
    for (int i = 0; i < len; i++)
    {
        int there = graph[here][i];
        if (there != parent)
            getTree(there, here);
    }
}
 
int main()
{
    int tCase;
    scanf("%d", &tCase);
 
    for (int tc = 1; tc <= tCase; tc++) {
        init();
        int n, m, a, b;
        scanf("%d %d %d %d", &n, &m, &a, &b);
 
        for (int i = 0; i < m; i++)
        {
            int from, to;
            scanf("%d %d", &from, &to);
            graph[from].push_back(to);
            graph[to].push_back(from);
            vc[from].push_back(to);
        }
        depth[0] = -1;
 
        getTree(1, 0);
 
        if (depth[a] != depth[b])
        {
            if (depth[a] > depth[b])
                swap(a, b);
 
            for (int i = max_level; i >= 0; i--)
            {
                if (depth[a] <= depth[ac[b][i]])
                    b = ac[b][i];
            }
        }
 
        int lca = a;
 
        if (a != b)
        {
            for (int i = max_level; i >= 0; i--)
            {
                if (ac[a][i] != ac[b][i])
                {
                    a = ac[a][i];
                    b = ac[b][i];
                }
                lca = ac[a][i];
            }
        }
 
        queue<int> q;
        q.push(lca);
        int subTree = 0;
        while (!q.empty()) {
            int here = q.front();
            q.pop();
            subTree++;
            for (int i = 0; i < vc[here].size(); i++)
                q.push(vc[here][i]);
        }
 
        printf("#%d %d %d\n", tc, lca, subTree);
    }
 
    return 0;
}