[UVA] 10158 - War

題目連結

題意：
a和b是朋友，b和c是朋友，則a和c也是朋友。
a和b是敵人，b和c是敵人，則a和c是朋友。
a和b是朋友，b和c是敵人，則a和c也是敵人。

==================================================
我的作法：
disjoint set，
將一群選出一個代表。
將朋友做union，另外用一個陣列存敵人，只需整群的代表存即可，
在做操作都是從代表去做。
==================================================
程式碼：
/* 題目: UVa 10158 - War
 * Language: C++
 * Created on: 2016年12月19日
 *   Author: hanting
 */
#include <iostream>
#include <vector>
using namespace std;
class DisjointSet
{
    vector<int> rep;
    vector<int> enemy;
    int id;
public:
    void init(int n)
    {
        id = 0;
        rep.assign(n, -1);
        enemy.assign(n, -1);
    }
    int Find(int x)
    {
        if(x < 0) return x;
        if(rep[x] < 0) return x;
        else return rep[x] = Find(rep[x]);
    }
    void Union(int x, int y)
    {
        if(x < 0 || y < 0) return ;
        int fx = Find(x),
            fy = Find(y);
        if(fx != fy)
        {
            if(rep[fx] <= rep[fy])
            {
                rep[fx] += rep[fy];
                rep[fy] = fx;
            }
            else
            {
                rep[fy] += rep[fx];
                rep[fx] = fy;
            }
        }
    }
    bool setFriend(int x, int y)
    {
        int fx = Find(x),
            fy = Find(y);
        if(enemy[fx] == fy) // x和y是敵人關係
        {
            return 0;
        }
        else // 分成x, y各自有不同敵人，或是x和y其中一個有敵人
        {
            Union(x, y);
            if(enemy[fx] != -1 && enemy[fy] != -1)
            {
                Union(enemy[fx], enemy[fy]);
                int fefx = Find(enemy[fx]);
                fx = Find(x);
                enemy[fx] = fefx;
                enemy[fefx] = fx;
            }
            else if(enemy[fx] != -1)
            {
                int efx = enemy[fx];
                fx = Find(x);
                enemy[fx] = efx;
            }
            else if(enemy[fy] != -1)
            {
                int efy = enemy[fy];
                fx = Find(x);
                enemy[fx] = efy;
            }
            return 1;
        }
    }
    bool setEnemy(int x, int y)
    {
        int fx = Find(x),
            fy = Find(y);
        if(fx == fy) // x和y是朋友
        {
            return 0;
        }
        else
        {
            Union(x, enemy[fy]);
            Union(y, enemy[fx]);
            fx = Find(x),
            fy = Find(y);
            enemy[fx] = fy;
            enemy[fy] = fx;
            return 1;
        }

    }
    bool areFriend(int x, int y)
    {
        int fx = Find(x),
            fy = Find(y);
        return fx == fy;
    }
    bool areEnemy(int x, int y)
    {
        int fx = Find(x),
            fy = Find(y);
        return Find(enemy[fx]) == fy;
    }
};
int main()
{
    int nodeN;
    cin >> nodeN;
    int op, s, t;
    DisjointSet dSet;
    dSet.init(nodeN);
    while(cin >> op >> s >> t && op+s+t)
    {
        switch(op)
        {
        case 1:
            if(!dSet.setFriend(s, t))
            {
                cout << -1 << endl;
            }
            break;
        case 2:
            if(!dSet.setEnemy(s, t))
            {
                cout << -1 << endl;
            }
            break;
        case 3:
            cout << dSet.areFriend(s, t) << endl;
            break;
        case 4:
            cout << dSet.areEnemy(s, t) << endl;
            break;
        }
    }
    return 0;
}