首页 > 代码库 > poj1703--Find them, Catch them

poj1703--Find them, Catch them

题意:一个城市n个犯罪嫌疑人,编号1-n,每次输入D x y表示x y属于同一帮派,A x y询问x y是否同一帮派或者不确定。

带权、种类并查集裸题,图片质量不好还请见谅。。oet[fx] = (oet[y]-oet[x]+d+2)%2   根据箭头关系就可以得出这个式子了,,加2是防止出现负值

 

#include <set>#include <map>#include <cmath>#include <ctime>#include <queue>#include <stack>#include <cctype>#include <cstdio>#include <string>#include <vector>#include <cstdlib>#include <cstring>#include <iostream>#include <algorithm>using namespace std;typedef unsigned long long ull;typedef long long ll;const int inf = 0x3f3f3f3f;const double eps = 1e-8;const int maxn =1e5+10;int n,m;int  pa[maxn],oet[maxn];void init(){    for (int i = 0; i < maxn; i++)    {        pa[i] = i;    }    memset(oet,0,sizeof(oet));}int find(int x){    if (pa[x] == x)    {        return x;    }    else    {        int tmp = pa[x];        pa[x] = find(tmp);        oet[x] = (oet[x]+oet[tmp])%2;        return pa[x];    }}void union_set(int x,int y,int d){    int fx = find(x);    int fy = find(y);    if (fx == fy)        return;    pa[fx] = fy;    oet[fx] = (oet[y]-oet[x]+d+2)%2;//oet[x] 表示x对其父亲的偏移量。至于这个式子怎么退出的,,就用向量来推,起点到终点}void query(int x,int y){    int fa = find(x);    int fy = find(y);    if (fa != fy)                       //x y不在一个集合中自然不能确定关系。    {         printf("Not sure yet.\n");         return;    }    int tmp = (oet[x]-oet[y]+2)%2;       //在求这种关系式的时候可以借助数学的向量来推导。    if (tmp==1)        printf("In different gangs.\n");    else        printf("In the same gang.\n");}int main(void){    int t;    cin>>t;    while (t--)    {        scanf("%d%d",&n,&m);        char ch[10];        int x,y;        init();        for (int i = 0; i < m; i++)        {            scanf("%s%d%d",ch,&x,&y);            if (ch[0]==‘A‘)            {                query(x,y);            }            else            {                union_set(x,y,1);            }        }    }    return 0;}

  

  

 

poj1703--Find them, Catch them