首页 > 代码库 > Uva 10158 War

Uva 10158 War

并查集的应用 直接阔成2倍。后N项为对应的敌人

#include <map>#include <set>#include <list>#include <cmath>#include <ctime>#include <deque>#include <stack>#include <queue>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <climits>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>#define LL long long#define PI 3.1415926535897932626using namespace std;int gcd(int a, int b) {return a % b == 0 ? b : gcd(b, a % b);}#define MAXN 10010int p[MAXN * 2];int Find(int x) {return x == p[x] ? x : p[x] = Find(p[x]);}int N,M;int main(){    //freopen("sample.txt","r",stdin);    while (scanf("%d",&N) != EOF)    {        for (int i = 0; i <= N * 2; i++) p[i] = i;        int op,x,y;        while (scanf("%d%d%d",&op,&x,&y) != EOF)        {            if (op == 0 && x == 0 && y == 0) break;            int  u = Find(x), v = Find(y);            int  eu = Find(x + N) , ev = Find(y + N);            switch (op)            {                case 1 : if (u == ev) puts("-1");                         else                         {                             p[u] = v;                             p[eu] = ev;                         }                         break;                case 2 : if (u == v) puts("-1");                         else                         {                             p[u] = ev;                             p[eu] = v;                         }                         break;                case 3 : if (u == v) puts("1");                         else puts("0");                         break;                case 4 : if (u == ev) puts("1");                         else puts("0");                         break;            }        }    }    return 0;}

 

Uva 10158 War