记录Kruscal易错点

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 500+5;
const int INF = ~0u>>2;
struct Node
{
    int u,v,w;
    bool operator < (const Node &a)const
    {
        return w < a.w;
    }
}node[25010];
int n,m,f[N];
int Find(int u)
{
    if(u == f[u])
      return f[u];
    return f[u] = Find(f[u]);
}
int Kruscal()
{
    int edge = 0,ans = 0;
    for(int i = 1;i <= n;++i)
       if(f[i] != i) edge++;
    for(int i = 0;i < m;++i){
       int faa = Find(node[i].u);
       int fab = Find(node[i].v);
       if(faa != fab){
          f[fab] = faa;
          edge++;
          ans += node[i].w;
       }
       if(edge == n-1)
         break;
    }
    if(edge == n-1)
      return ans;
    else
      return -1;
}
int main()
{
//    freopen("Input.txt","r",stdin);
    int T,k;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&m,&k);
        int a,b,t,faa,fab;
        for(int i = 0;i <= n;++i) f[i] = i;
        for(int i = 0;i < m;++i)
        {
            scanf("%d%d%d",&node[i].u,&node[i].v,&node[i].w);
        }
        while(k--)
        {
            scanf("%d",&t);
            scanf("%d",&a);
            faa = Find(a);     
            for(int i = 1;i < t;++i){
               scanf("%d",&b);
               fab = Find(b);  
               if(fab != faa)
                 f[fab] = faa;        //以前都没用过并查集，来做Kruscal。忘记了要跟新的是父亲f[fab] = faa!!!!!
            }
        }
        sort(node,node+m);
        printf("%d\n",Kruscal());
    }
    return 0;
}

 题目链接：Click Here~

记录Kruscal易错点

原文：http://blog.csdn.net/zhongshijunacm/article/details/19498899