[HDU1272] 소희의 미로 문제풀이 보고서, 데이터+사고방식+코드

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#define INPUT
using namespace std;
/*
    Problem : HDU1272 -      
    State   ：
    5421320	2012-02-26 23:40:14	Accepted	1272	62MS	1636K	3853 B	G++	c0de4fun
    Begin Time:26th/2/2012 9:30 p.m;
    End Time:26th/2/2012 11:43 p.m
    Cost Time: 2 hrs 13 mins;
        ：
1 4 1 2 2 12 12 13 12 15 15 11 11 3 3 2 4 5 5 9 5 6 6 7 6 8 9 10
0 0
1 2 1 3 1 4 2 8 8 9 3 5 5 10 10 12 4 6 6 11 4 7
0 0
1 2 3 1 4 1 8 2 8 9 5 3 5 10 10 12 6 4 6 11 4 7
0 0
1 4 2 1 2 12 12 13 15 12 15 11 11 3 2 3 4 5 5 9 5 6 6 7 6 8 9 10
0 0
6 8  5 3  5 2  6 4
5 6  0 0
8 1  7 3  6 2  8 9  7 5
7 4  7 8  7 6  0 0
3 8  6 8  6 4
5 3  5 6  5 2  0 0
1 2 3 4 0 0
1 2 0 0
-1 -1
    Output:
No
Yes
Yes
No
Yes
Yes
No
No
Yes
      ：
         。
           ，      ，  parent     。
      ，             ，   Exceeded。
         while   。
         i,j      ：
    （1）i  ，j   
        j       
     nodes[j].parent = findSet(nodes[i]);
        ，   nodes[i] parent  ，  
     counts++，      ，    Rank.
     nodes[nodes[j].parent].rank++;
       “  ” Rank           ，    
     （2）j  ，i   
      （1）  ，    
     nodes[i].parent = findSet(nodes[j]);
     counts++;
     nodes[nodes[i].parent].rank++;
    （3）j  ，i  
          
         nodes[j].parent      nodes[i].parent
          ，  fail = true;
           
       Union，Union    j,i parent
       Linked   Parent，Parent Rank      
         “  ”，     Rank  ，  head  
         
     （4）i,j    
           j parent = i，
     【      findSet!!!!】
        head = i！！
     ——————————————————————————
           ，    findSet   ，    
            “  ”   。            
         ，  ，    head  ，       。
            Rank       count       
         ，        ，   Fail = true;

       ，i,j       head = i    1 2 0 0   No
     ———————————————————————————
          
           head      Rank      count       
     fail，    ，  fail = true;
            fail i  ，j     findSet        
     if(fail) print No
     else print Yes

     Have fun,c0de4fun.
*/
const int MAX_SIZE = 100010;
struct node
{
    int parent;
    int val;
    int rank;
};
node nodes[MAX_SIZE];
int allRank = 0;
//bool Unioned = false;
bool fail = false;
int head = 0;
void Link(int x,int y)
{
    if(nodes[x].rank > nodes[y].rank)
    {
        nodes[y].parent = x;
        nodes[x].rank = nodes[x].rank + nodes[y].rank;
        allRank = nodes[x].rank;
        head = x;
    }
    else
    {
        nodes[x].parent = y;
        nodes[y].rank = nodes[y].rank + nodes[x].rank;
        allRank = nodes[y].rank;
        head = y;
    }
}
int findSet(node* n)
{
    node tmp;
    tmp = *n;
    while(tmp.val != tmp.parent)
    {
        tmp = nodes[tmp.parent];
    }
    n->parent = tmp.val;
    head = tmp.val;
    return tmp.val;
}
void Union(node *i,node *j)
{
 //   Unioned = true;
    Link(findSet(i),findSet(j));
}
int main(int argc,char* argv[])
{
    int i,j,count = 0;
#ifdef INPUT
    freopen("b:\\acm\\hdu1272\\input.txt","r",stdin);
#endif
    while(scanf("%d%d",&i,&j)!= EOF)
    {
        if( i != - 1 && j != -1)
        {
            if( i != 0 && j != 0 )
            {
                //Judge if i already existed.
                if(nodes[i].val == 0)
                {
                    //Not Existed.
                    //makeSet(nodes[i])
                    nodes[i].parent = i;
                    nodes[i].val = i;
                    nodes[i].rank = 1;
                    count++;
                    if(nodes[j].val == 0)
                    {
                        nodes[j].parent = i;
                        nodes[j].val = j;
                        nodes[i].rank++;
                        head = i;
                        count++;
                    }
                    else
                    {
                        //node[i].parents = j!
                     //  nodes[i].parent = findSet(&node[j]);
                       nodes[i].parent = findSet(&nodes[j]);
                       nodes[i].val = i;
                       nodes[nodes[i].parent].rank++;
                    }
                }
                else //Already Existed
                {
                 //   nodes[j].parent = i;
                    if(nodes[j].val != 0)
                    { // To see if nodes[j] existed
                        //Yes
                        nodes[j].val = j;
                       // nodes[j].parent = i;
                          findSet(&nodes[j]);
                        if (nodes[j].parent == nodes[i].parent)
                            fail = true;
                        else
                            Union(&nodes[j],&nodes[i]);
                    }
                    else
                    {  //No
                        nodes[j].parent = i;
                        nodes[j].val = j;
                        findSet(&nodes[j]);
                        nodes[nodes[j].parent].rank++;
                        count++;
                    }
                }

            }
            else
            {
            /*  if(Unioned)
                {
                    if(allRank < count)
                        fail = true;
                } */
             //head     ！
                if(nodes[head].rank < count)
                    fail = true;
                if(fail)
                   printf("No
");
                else
                   printf("Yes
");
                ////Judge now¡ü
                fail = false;
                allRank = 0;
                count = 0;
                Unioned = false;
                head = 0;
                memset(nodes,0,sizeof(node)*MAX_SIZE);
            }
        }
    }
    return 0;
}