Boj 13306, 34203 오프라인 쿼리 c++

13306 트리

https://www.acmicpc.net/problem/13306

 

문제

1 <= N, Q <= 200000

입력은 노드가 N개인 트리에 대한 정보가 각 노드의 부모노드로 주어진다.

다음 Q+N-1개의 줄에는 총 2가지의 쿼리가 주어진다.

1번 질의 : 0 x   x번 노드와 해당 노드의 부모노드를 연결하는 간선을 삭제한다.

2번 질의 : 1 a b   a번 노드와 b번 노드를 잇는 경로가 존재하는지에 대한 여부를 묻는다.

 

매번 2번 질의에 대하여 이전의 작업들을 반영하여 정답을 출력하면 된다.

단, 간선을 삭제하는 질의는 총 N-1번 주어진다.

 

접근 & 풀이

두 노드가 연결되어있는지 분리되어있는지 여부는 분리집합으로 확인하면 편하다.

하지만 분리집합에서 간선을 삭제하기란 매우 어렵다. 

이미 연결되어있는 상태에서 간선을 제거하면, 각 노드 사이의 연결 정보를 업데이트해야 하기 때문에 시간복잡도가 증가한다.

 

그래프 상에서 간선에 대한 작업에 있어서는 간선 제거보다 간선 추가가 더 쉽다는 것을 명심해두자.

 

 

해당 문제에서는 결국 N-1번의 작업을 통해서 트리의 모든 간선을 제거한다.

그렇다면 모든 질의를 거꾸로 생각해보면, 모든 노드가 연결되지 않은 초기 상태에서 1번 질의는 두 노드를 연결하는 작업에 해당한다.

 

때문에, 2번 질의 또한 처리하기 매우 쉬워지는 것이다.

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int parent[200001], tree[200001];
vector<string> ans;

int Find(int x) {
    if(parent[x] == x)
        return x;
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

bool Is_Same(int a, int b) {
    return Find(a) == Find(b);
}

int main() {
    int N, Q;

    cin >> N >> Q;

    for(int i = 1; i <= N; i++) {
        parent[i] = i;
    }

    for(int i = 2; i <= N; i++) {
        int x;
        cin >> x;
        tree[i] = x;
    }

    vector<int> query[N+Q];


    for(int i = 0; i < N+Q-1; i++) {
        int t, x, a, b; cin >> t;
        if(t == 0) {
            cin >> x;
            query[i] = {t, x};
        }
        else {
            cin >> a >> b;
            query[i] = {t, a, b};
        }
    }
    for(int i = N+Q-2; i >= 0; i--) {
        if(query[i][0] == 0) {
            int x;
            x = query[i][1];
            Union(x, tree[x]);
        }
        else {
            int a, b;
            a = query[i][1];
            b = query[i][2];
            if(Is_Same(a, b))
               ans.push_back("YES");
            else
                ans.push_back("NO");
        }
    }
    for(int i = Q-1; i >= 0; i--) {
        cout << ans[i] << "\n";
    }

}

 

 

 

34203 통행료

https://www.acmicpc.net/problem/34203

 

 

시간이 지남에 따라 각 간선의 가중치가 0에서 1로 변할 때 각각의 그래프 상에서의 모든 경로의 합을 구하는 문제이다.

N제한이 매우 작아서 플로이드 워셜을 사용할 수 있다.

 

하지만 이 문제의 경우에는 직관적으로 생각하면 가중치가 1인 간선을 '추가' 하는 것이지만, 

각각의 경로를 기준으로 생각하면 0으로 지날 수 있던 경로에 1을 더하여 가중치가 0인 간선을 '제거' 하는 것으로 

생각하는 것이 더 문제를 풀기에 쉬워진다.

 

때문에, 해당 문제 또한 간선에 가중치를 추가하는 작업을 거꾸로 수행하면 

모든 가중치가 1인 상태에서  가중치가 0인 간선을 추가하는 형태로 진행하면,

이전에는 필요했던 여러가지 불필요한 작업들을 하지 않아도 된다.

 

자세한 원리는 이후에 추가하겠다.

 

전체코드

#include <bits/stdc++.h>
#define inf 99999999
#define int long long
#define fastio ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
using namespace std;

int dist[501][501], parent[501];

int Find(int x) {
    if(x == parent[x])
        return x;
    return parent[x] = Find(parent[x]);
}

void Union(int a, int b) {
    a = Find(a);
    b = Find(b);
    parent[a] = b;
}

bool Is_Same(int a, int b) {
    return Find(a) == Find(b);
}

int32_t main() {
    fastio

    int N, M;

    cin >> N >> M;

    vector<int> query[M];

    for(int i = 1; i <= N; i++)
        parent[i] = i;

    for(int i = 1; i <= N; i++)
        for(int j = 1; j <= N; j++)
            if(i!=j)dist[i][j] = inf;

    for(int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        dist[a][b] = 1;
        dist[b][a] = 1;
        query[i] = {a, b};
    }
    for(int i = 1; i <= N; i++) {
        for(int j = 1; j <= N; j++) {
            for(int k = 1; k <= N; k++) {
                dist[j][k] = min(dist[j][k], dist[j][i] + dist[i][k]);
            }
        }
    }

    vector<int> ans(M, 0);

    for(int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            ans[0] += dist[i][j];
        }
    }
    int cnt = 0, stpoint;
    for(int i = M-1; i > 0; i--) {
        if(cnt>= N-1) {
            ans[M-i] = 0;
            continue;
        }
        int a, b;
        a = query[i][0];
        b = query[i][1];

        if(Is_Same(a, b)) {
            ans[M-i] = ans[M-i-1];
            continue;
        }

        Union(a, b); cnt++;
        for(int j = 1; j <= N; j++) {
            for(int k= 1; k <= N; k++) {
                dist[j][k] = min({dist[j][k], dist[j][a] + dist[b][k], dist[j][b] + dist[a][k]});
            }
        }
        for(int j = 1; j <= N; j++) {
            for (int k = 1; k <= N; k++) {
                ans[M-i] += dist[j][k];
            }
        }
    }

    for(int i = M-1; i >= 0; i--) {
        cout << ans[i] << "\n";
    }
}

 

1월에 PS를 너무 안한 것 같다. 앞으로 열심히 하겠다.