Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

为何总是WA呢?--------郁闷,第一次写并查集

Posted by kamake at 2011-03-29 19:14:57 on Problem 1611
#include<iostream>
using namespace std;
int rank[30001];
int cluster[30001];
int findCluster(int pos)
{
     if(cluster[pos]==pos)
     {
                        return pos;
     }
     return cluster[pos]=findCluster(cluster[pos]);
}
void Merge(int i1,int i2)
{
    int j1=findCluster(i1);
    int j2=findCluster(i2);
    
    if(j1==j2)
       return; 
    if(rank[j1]>rank[j2])
    {
       cluster[i2]=j1;
    }
    else
    {
        cluster[i1]=j2;
        if(rank[j1]==rank[j2])
        {
                              rank[j2]++;
        }
    }
}
//利用并查集来解POJ1611问题 
void func(int N,int K)
{
     //看了蜗居,人生真是艰难 
     //初始化 
     for(int i=0;i<30001;i++)
         cluster[i]=i;
     for(int i=0;i<30001;i++)
         rank[i]=0;
     
     for(int k=0;k<K;k++)
     {
             int temp;
             cin>>temp;
             int temp1;
             cin>>temp1;
             for(int i=1;i<temp;i++)
             {
                    int temp2;
                    cin>>temp2;
                    Merge(temp1,temp2);
             }
     }
     int sum=0;
     for(int i=0;i<N;i++)
     {
             if(findCluster(i)==findCluster(0))
             {
                  sum++;
             }
     }
     cout<<sum<<endl;
}
int main()
{
    int N,K;
    cin>>N;
    cin>>K;
    while(true)
    {
         if(N==0&&K==0)
         {
                       break;
         }
         if(K==0)
         {
                 cout<<"1"<<endl;
                 
         }
         else
         {
                  func(N,K);
         }
         cin>>N>>K;
    } 
    system("pause");
    return 0;
} 

Followed by:

Post your reply here:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator