keymasterviriya1150

Untitled

Sep 8th, 2016
161
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.11 KB | None | 0 0
  1. #include<iostream>
  2. using namespace std;
  3. class QuickFind
  4. {
  5. private:
  6.     int *id, size;
  7. public:
  8.     QuickFind(int N)
  9.     {
  10.         id = new int[N];   
  11.         size = N;
  12.         for (int i = 0; i < N; i++)
  13.             id[i] = i;
  14.     }
  15.  
  16.     bool find(int p, int q)
  17.     {   return id[p] == id[q];  }
  18.  
  19.     void unite(int p, int q)
  20.     {
  21.         int pid = id[p];
  22.         for (int i = 0; i < size; i++)
  23.             if (id[i] == pid)
  24.                 id[i] = id[q];
  25.         /*
  26.            
  27.         */
  28.            
  29.     }
  30.     /*
  31.     3-4   0 1 2 4 4 5 6 7 8 9
  32.     4-9   0 1 2 9 9 5 6 7 8 9
  33.     8-0   0 1 2 9 9 5 6 7 0 9
  34.     2-3   0 1 9 9 9 5 6 7 0 9
  35.     5-6   0 1 9 9 9 6 6 7 0 9
  36.     5-9   0 1 9 9 9 9 9 7 0 9
  37.     7-3   0 1 9 9 9 9 9 9 0 9
  38.     4-8   0 1 0 0 0 0 0 0 0 0
  39.     6-1   1 1 1 1 1 1 1 1 1 1
  40.         Problem: many value can change
  41.    
  42.     */
  43. };
  44. class  QuickUnion
  45. {
  46.     private:
  47.     int *id, size;
  48.  
  49.     int root(int i)    /*QuickUnion add  fuction  root
  50.                          ============diffence==============*/
  51.     {
  52.         while (i != id[i])
  53.             i = id[i];
  54.         return i;
  55.     }
  56.  
  57.     public:
  58.     QuickUnion (int N)
  59.     {
  60.         id = new int[N];   
  61.         size = N;
  62.         for (int i = 0; i < N; i++)
  63.             id[i] = i;
  64.     }
  65.  
  66.     bool find(int p, int q)
  67.     {
  68.         return root(p) == root(q);
  69.     }
  70.  
  71.     void unite(int p, int q)
  72.     {
  73.         id[root(q)] = root(p);
  74.     }
  75.     /*
  76.         3-4   0 1 2 4 4 5 6 7 8 9
  77.         4-9   0 1 2 9 9 5 6 7 8 9
  78.         8-0   0 1 2 9 9 5 6 7 0 9
  79.         2-3   0 1 9 9 9 5 6 7 0 9
  80.         5-6   0 1 9 9 9 6 6 7 0 9
  81.         5-9   0 1 9 9 9 9 9 7 0 9
  82.         7-3   0 1 9 9 9 9 9 9 0 9
  83.         4-8   0 1 0 0 0 0 0 0 0 0
  84.         6-1   1 1 1 1 1 1 1 1 1 1
  85.     */
  86. };
  87. class WeightedQuickUnion
  88. {
  89.     private:
  90.             int *id,*sz,size;
  91.             int root(int i)
  92.             {
  93.                 while(i!=id[i])
  94.                     i=id[i];
  95.                 return i;
  96.             }
  97.     public:
  98.         WeightedQuickUnion(int N)
  99.             {
  100.                 id=new int [N];
  101.                 sz=new int [N];
  102.                 size=N;
  103.                 for(int i=0;i<N;i++)           
  104.                 {
  105.                     id[i]=i;
  106.                     sz[i]=i;
  107.                 }
  108.                    
  109.             }
  110.             bool find(int p,int q)
  111.             {
  112.                 return root(p)==root(q);   
  113.             }
  114.             void uinte(int p,int q) // cheak connected
  115.             {
  116.                 /* WeightedQuickUnion add Weighted
  117.                 ============diffence==============*/
  118.                 int x = root(p);
  119.                 int y = root(q);
  120.                 if(sz[x] < sz[y])
  121.                 {
  122.                     id[x] = y;
  123.                     sz[y] += sz[x];
  124.                 }
  125.                 else
  126.                 {
  127.                     id[y] = x;
  128.                     sz[x] += sz[y];
  129.                 }
  130.             }          
  131. };
  132. class PathCompression
  133. {
  134.     private:
  135.             int *id,size;
  136.             int root(int i)
  137.             {
  138.                 while(i!=id[i])
  139.                 {
  140.                     id[i] = id[id[i]];
  141.                     i=id[i]; /*============diffence==============*/
  142.                 }
  143.                    
  144.                 return i;
  145.             }
  146.     public:
  147.             PathCompression(int N)
  148.             {
  149.                 id=new int [N];
  150.                 size=N;
  151.                 for(int i=0;i<N;i++)
  152.                     id[i]=i;
  153.             }
  154.             bool find(int p,int q)
  155.             {
  156.                 return root(p)==root(q);   
  157.             }
  158.             void uinte(int p,int q) // cheak connected
  159.             {
  160.                 id[root(q)]=root(p);
  161.             }              
  162. };
  163. class WQUPC
  164. {
  165.     private:
  166.             int *id,*sz;
  167.             int root(int i)
  168.             {
  169.                 while(i!=id[i])
  170.                 {
  171.                     id[i] = id[id[i]];
  172.                     i=id[i];
  173.                 }
  174.                    
  175.                 return i;
  176.             }
  177.     public:
  178.         WQUPC(int N)
  179.         {
  180.             id=new int [N];
  181.             sz=new int [N];
  182.    
  183.             for(int i=0;i<N;i++)           
  184.             {
  185.                 id[i]=i;
  186.                 sz[i]=i;
  187.             }
  188.         }
  189.             bool find(int p,int q)
  190.             {
  191.                 return root(p)==root(q);   
  192.             }
  193.             void unite(int p,int q) // cheak connected
  194.             {
  195.                 int i = root(p);
  196.                 int j = root(q);
  197.  
  198.  
  199.  
  200.                 if(sz[i] < sz[j])
  201.                 {          
  202.  
  203.                     id[i] = j;
  204.                     sz[j] += sz[i];
  205.  
  206.                 }
  207.                 else
  208.                 {
  209.                     id[j] = i;
  210.                     sz[i] += sz[j];
  211.                 }
  212.             }              
  213. };
  214. void inputWQUPC()
  215. {
  216.     int N;
  217.     cin >>N;
  218.     WQUPC uf(N+1);
  219.     char op;
  220.     while(cin>>op)
  221.     {
  222.         int p,q;
  223.         cin >>p>>q;
  224.         if(op=='c')
  225.             uf.unite(p,q);
  226.         else if(op=='q')
  227.         {
  228.             if(uf.find(p,q))
  229.                 cout << p << " and " << q <<" are connected.\n";
  230.             else
  231.                 cout << p << " and " << q <<" are isolated.\n";
  232.         }
  233.         else break;
  234.     }
  235.     /*
  236.         10
  237.         c 3 4
  238.         c 4 9
  239.         q 5 3
  240.             5 and 3 are connected
  241.         c 8 0
  242.         q 9 3
  243.             5 and 3 are connected
  244.         c 2 3
  245.         c 5 6
  246.         c 5 9
  247.         q 3 5
  248.             5 and 3 are connected
  249.         q 5 2
  250.             5 and 3 are connected
  251.         c 7 3
  252.         c 4 8  
  253.         q 1 7
  254.             5 and 3 are connected
  255.         q 8 2
  256.             5 and 3 are connected
  257.         c 6 1
  258.         q 1 3
  259.             5 and 3 are connected
  260.         x 0 0
  261.         time 3.42
  262.     */
  263. }
  264. int main()
  265. {
  266.     inputWQUPC();
  267. }
Advertisement
Add Comment
Please, Sign In to add comment