当前位置：首页 -> 基础 -> c++编程基础

UVA 10158 - War(并查集)(二)

2014-11-24 02:44:47 · 作者: · 浏览: 3
标签: UVA 10158 War 查集
对，3询问是否结盟，4询问是否敌对。如果有矛盾的情况输出-1，询问正确输出1失败输出0.
思路：并查集，0 - n代表结盟集合，n - 2n代表敌对集合。
代码： 
#include   
#include   
const int N = 20005;  
  
int n, q, a, b, parent[N];  
  
int find(int x) {  
    if (x != parent[x]) return parent[x] = find(parent[x]);  
    else return x;  
}  
  
void init() {  
    for (int i = 0; i < n; i ++) {  
        parent[i] = i;  
        parent[i + n] = i + n;   
    }  
}  
  
void solve() {  
    int a1 = find(a); int a2 = find(a + n);  
    int b1 = find(b); int b2 = find(b + n);  
    if (q == 1) {  
        if (a1 == b2) printf("-1\n");  
        else {  
            parent[a1] = b1;  
            parent[a2] = b2;  
        }  
    }  
    if (q == 2) {  
        if (a1 == b1) printf("-1\n");  
        else {  
            parent[a1] = b2;  
            parent[a2] = b1;  
        }  
    }  
    if (q == 3) {  
        if (a1 == b1) printf("1\n");  
        else printf("0\n");  
    }  
    if (q == 4) {  
        if (a1 == b2) printf("1\n");  
        else printf("0\n");  
    }  
}  
  
int main() {  
    while (~scanf("%d", &n)) {  
        init();  
        while (~scanf("%d%d%d", &q, &a, &b) && q) {  
            solve();  
        }  
    }  
    return 0;  
}