HDU 1232 畅通工程

#include <cstdlib>
#include <iostream>
using namespace std;
const int MAX = 1001;
int unionSets[MAX];

int findRoot(int x)
{
    if(unionSets[x] == -1)
    {
        return x;
    }
    else
    {
        int tem = findRoot(unionSets[x]);//递归调用直到找到根
        unionSets[x] = tem;//把沿途的都指向根
        return tem;//返回根
    }
}
int main()
{
    int N, M, a, b;
    int root1, root2;
    while(cin >> N && N)
    {
        cin >> M;
        for(int i = 0; i < MAX; ++i)
            unionSets[i] = -1;
        for(int i = 0; i < M; ++i)
        {
            cin >> a >> b;
            root1 = findRoot(a);
            root2 = findRoot(b);
            if(root1 != root2)
            {
                unionSets[root1] = root2;//两个集合合并在一起
            }
        }
        int ans = 0;
        for(int i = 1; i <= N; ++i)
        {
            if(unionSets[i] == -1)
            {
               ans++;
            }
        }
        cout << ans - 1 << endl;
    }
    return 0;
}

#include <iostream>
#include <cstdio>

using namespace std;

const int MAXN = 1003;
int p[MAXN];

void makeSet(int n)
{     for(int i=1;i<=n;i++)         p[i] = i;
}

int findFather(int x)
{     int a = x;     while(a != p[a])     {         int t = a;         a = p[a];         p[t] = a;     }     return a;
}

void Union(int a, int b)
{     int fa = findFather(a);     int fb = findFather(b);     if(fa != fb)         p[fa] = fb;
}

int main()
{     int N,M;     while(scanf("%d%d", &N, &M)!=EOF && N)     {         int cnt = 0;         makeSet(N);         for(int i=0;i<M;i++)         {             int a,b;             scanf("%d%d", &a, &b);             Union(a,b);         }                  for(int i=1;i<=N;i++)             if(findFather(i) == i)                 cnt++;         cout<<cnt-1<<endl;     }     return 0;
}

#include<iostream>

#include<string>

using namespace std;

int findRoot(int *tree,int index)

{

    if(tree[index]==-1) return index;

    else

    {

        int tmp = findRoot(tree,tree[index]);

        tree[index] = tmp;

        return tmp;

    }

}

int main()

{

    while(1)

    {

        int N,M;//N城市数目M道路数目

        scanf("%d",&N);

        if(N==0)break;

        int *tree = new int[N+1];

        for(int i=1;i<=N;i++)

        {

            tree[i]=-1;

        }

        scanf("%d",&M);

        for(int i=0;i<M;i++)

        {

            int a,b;

            scanf("%d %d",&a,&b);

            a= findRoot(tree,a);

            b= findRoot(tree,b);

            if(a!=b)

            {

                tree[a]=b;

            }

            //cout<<"M:"<<M<<" N:"<<N<<" a="<<a<<",b="<<b<<endl;

        }

        int sum = 0;

        for(int i=1;i<=N;i++)

        {

            if(tree[i]==-1)

                sum++;

        }

        cout<<sum-1<<endl;

    }

    return 0;

}

Huge input, scanf is recommanded...

#include <iostream>
using namespace std;
const int N = 1000+5;

int tree[N];

int findroot(int x) {
    if (tree[x] == -1) return x;
    else {
        //temp中保存的是树的根节点下标
        int temp = findroot(tree[x]);
        tree[x] = temp;
        return temp;
    }
}

int main() {

    int n;
    while (cin >> n) {
        if (n == 0) break;
        int m;
        cin >> m;
        for (int i = 1; i <= n; i++) tree[i] = -1;
        while (m--) {
            int a, b;
            cin >> a >> b;
            a = findroot(a);
            b = findroot(b);
                   //在a和b不相等时才需要连接，否则不用连接
            if (a != b) {
                tree[a] = b;
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            if (tree[i] == -1) {
                ans++;
            }
        }

        cout << ans-1 << endl;
    }
    return 0;
}

	

#include <iostream>
#include <map>
using std::map;      namespace UNIONFIND{     template<class Type>     class UnionFind{         public:             UnionFind(){}             UnionFind(const int size, const Type * datas){                 init(size, datas);             }                          ~UnionFind(){                 delete [] m_flag;                 delete [] m_record;             }                          void init(const int size, const Type * datas){                 m_size = size;                 m_record = new Record [size];                 m_flag = new int [size];                 for(int i = 0; i < size; ++i){                     m_flag[i] = i;                     m_record[i].root = i;                     m_record[i].data = datas[i];                     m_map_index[datas[i]] = i;                 }             }                          bool is_union(const Type & data_a, const Type & data_b){                 return is_union_fromIndex(m_map_index[data_a], m_map_index[data_b]);             }                          bool union_element(const Type & data_a, const Type & data_b){                 return union_element_fromIndex(m_map_index[data_a], m_map_index[data_b]);             }                          bool is_union_fromIndex(const int index_a, const int index_b){                 return m_record[index_a].root == m_record[index_b].root;             }                          bool union_element_fromIndex(const int index_a, const int index_b){                 if(index_a < 0 || index_a >= m_size){                     return false;                 }else if(index_b < 0 || index_b >= m_size){                     return false;                 }                                  int root_a = find_root(index_a);                 int root_b = find_root(index_b);                                  if(root_a != root_b){                     int height_a = m_record[root_a].height;                     int height_b = m_record[root_b].height;                     if(height_a == height_b){                         ++m_record[root_a].height;                         m_record[root_b].root = root_a;                     }else {                         height_a > height_b ?                              m_record[root_b].root = root_a                              :                             m_record[root_a].root = root_b;                     }                 }                                  return true;                              }                          bool is_root(const int index){                 return m_record[index].root == index;             }                      private:             int find_root(const int index){                 return m_record[index].root == index ?                      index : m_record[index].root = find_root(m_record[index].root);             }                          private:             struct Record{                 int height = 0;                 int root;                 Type data;             };                          map<Type, int> m_map_index;             int * m_flag = nullptr;             Record * m_record = nullptr;             int m_size = 0;     };

};

using namespace UNIONFIND;
const int N = 1006;

int main(int argc, char** argv) {          int n, m;     int arr[N];     int a, b;     UnionFind<int> union_find;     while(scanf("%d", &n), n){         scanf("%d", &m);                  for(int i = 0; i < n; ++i){             arr[i] = i;         }                  union_find.init(n, arr);                  for(int i = 0; i < m; ++i){             scanf("%d %d", &a, &b);             union_find.union_element_fromIndex(a-1, b-1);         }                  int cal_roots = 0;         for(int i = 0; i < n; ++i){             if(union_find.is_root(i)){                 ++cal_roots;             }          }                  printf("%d\n", cal_roots-1);     }          return 0;
}

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int findHead(vector<int> &arr,int val){
    if(arr[val]==-1) return val;
    int head = findHead(arr,arr[val]);
    arr[val]=head;
    return head;
}
int main(){
    int N,M;
    scanf("%d",&N);
    while(N>0){
        scanf("%d",&M);
        // 小优化1：当M==0或M==1时可以直接求出结果
        if(M==0 || M==1){
            printf("%d\n",N-1-M);
            scanf("%d",&N);
            continue;
        }
        vector<int> arr(1002,-1);
        int v1,v2;
        //小优化2：可以记录下输入节点中的最大值和最小值
        int nmin=N+1,nmax=-1;
        int a,b;
        for(int i=0;i<M;i++){
            scanf("%d%d",&v1,&v2);
            nmin = min(min(v1,v2),nmin);
            nmax = max(max(v1,v2),nmax);
            v1 = findHead(arr,v1);
            v2 = findHead(arr,v2);
            if(v1!=v2){
                arr[v1] = v2;
            }
        }
        int head;
        //在最大值和最小值之外的节点肯定没有被修改，等于-1
        int count = nmin-1 + N-nmax;
        for(int i=nmin;i<=nmax;i++){
            if(arr[i]==-1) count++;
        }
        printf("%d\n",count-1);
        scanf("%d",&N);
    }
    return 0;
}

import java.util.Scanner;

/**
 * Created by jxuan on 16-4-1.
 * 某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省***“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？
 */
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            int N = in.nextInt();
            if (N == 0) {
                break;
            }
            int M = in.nextInt();
            int[] pro = new int[N + 1];
            for (int i = 1; i < pro.length; i++) {
                pro[i] = i;
            }
            while (M > 0) {
                int a = in.nextInt();
                int b = in.nextInt();
                combain(a, b, pro);

                M--;
            }
            int count = -1;//因为最终的跟节点的pro一定是它本身，所以需要减掉一个次数
            for (int i = 1; i < pro.length; i++) {
                if (pro[i] == i) {
                    count++;
                }
            }
            System.out.println(count);
        }
    }

    public static void combain(int x, int y, int[] pro) {
        int a, b;
        a = find(pro, x);
        b = find(pro, y);
        if (a != b) {
            pro[a] = b;
        }
    }

    public static int find(int[] pro, int x) {
        if (pro[x] != x) {
            pro[x] = find(pro, pro[x]);
        }
        return pro[x];
    }

}