poj1703-白红宇

poj1703

阅读量：6251 次

发布时间：2019-06-22

本文共 921 字，大约阅读时间需要 3 分钟。

题目大意：一共有两个类，两种操作D X Y表示X Y在不同的类里面，A X Y 询问X Y之间的关系(未知，相同，不同)

分析：简单带权并查集，D[i]表示与i对立的类，维护好这个变量就可以了。

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 #include 
         
           5 #include 
          
            6 #include 
            7 #include 
            
              8 #include
             
               9 #define maxn 10001010 #define maxm 10001011 #define mod 100000000000000000012 #define INF 0x3fffffff13 using namespace std;14 int father[maxn];15 int n;16 int d[maxn];17 void init(){18 for(int i=0;i<=n;++i){19 father[i]=i;20 d[i]=-1;21 }22 }23 int Find(int x){24 return father[x]==x?x:father[x]=Find(father[x]);25 }26 void Union(int x,int y){27 x =Find(x);28 y =Find(y);29 if(x!=y)father[x]=y;30 }31 int main ()32 {33 int t,m;34 scanf("%d",&t);35 while(t--){36 scanf("%d%d",&n,&m);37 init();38 char ch[10];39 int x,y;40 for(int i=0;i