首页 > 代码库 > hdu 1213 -how many tables

hdu 1213 -how many tables

凭记忆打的代码,在学数据结构的时候,用下标索引的方法进行合并,即将相同集合中的数据归为一颗树中的节点,当进行判断的时候,分别找父亲,若是同一个父亲就不用归并,否则就归并。用数组就可以了。

#include<iostream>using namespace std;int index[1001];int getfather(int n){    while(index[n] != n)    {        n = index[n];    }    return n;}int main(){    int m; cin >> m;    while(m--)    {       int peo,pair;;       cin >> peo >> pair;       for(int i = 1;i <= peo;i++)       {           index[i] = i;       }       int fathera;       int fatherb;       for(int j = 0;j < pair;j++)       {           int a,b;           cin >> a >> b;           fathera = getfather(a);           fatherb = getfather(b);           if(fathera != fatherb)           {               index[fatherb] = fathera;           }       }       int count = 0;       for(int i = 1;i <= peo;i++)       {           if(i == index[i])           {               count++;           }       }       cout << count << endl;    }    return 0;}