Poj 1703: Find them, Catch them

poj1703.md

Poj 1703: Find them, Catch them

題目

分析

poj 1182 弱化版…同樣的想法照著做就是了

AC Code

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cstdlib>

using namespace std;

const int MAX_N = 100000;
int N, M;

int parent[MAX_N * 2];
int height[MAX_N * 2];

void init() {
    for (int i = 0; i < 2 * N; i++) {
        parent[i] = i;
        height[i] = 0;
    }
}

int find(int a) {
    if (parent[a] == a)
        return a;
    return parent[a] = find(parent[a]);
}

void unite(int a, int b) {
    a = find(a);
    b = find(b);
    if (a == b) return;
    if (height[a] < height[b])
        parent[a] = b;
    else {
        parent[b] = a;
        if (height[a] == height[b]) height[a]++;
    }
}

bool same(int a, int b) {
    return find(a) == find(b);
}

int main() {
    int T;
    scanf("%d", &T);

    while (T--) {
        scanf("%d %d\n", &N, &M);

        init();

        for (int i = 0; i < M; i++) {
            char query; int a, b;
            scanf("%c %d %d\n", &query, &a, &b);
            a--; b--;

            if (query == 'D') {
                unite(a, b + N);
                unite(a + N, b);
            }
            else {
                if (same(a, b + N) || same(a + N, b))
                    puts("In different gangs.");
                else if (same(a, b) || same(a + N, b + N))
                    puts("In the same gang.");
                else
                    puts("Not sure yet.");
            }
        }
    }

    return 0;
}