首页 > 试题广场 >

HDU 1232 畅通工程

[编程题]HDU 1232 畅通工程
  • 热度指数：356 时间限制：C/C++ 2秒，其他语言4秒 空间限制：C/C++ 32M，其他语言64M
  • 算法知识视频讲解
某省调查城镇交通状况，得到现有城镇道路统计表，表中列出了每条道路直接连通的城镇。省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通（但不一定有直接的道路相连，只要互相间接通过道路可达即可）。问最少还需要建设多少条道路？

输入描述:
测试输入包含若干测试用例。每个测试用例的第1行给出两个正整数，分别是城镇数目N ( < 1000 )和道路数目M；随后的M行对应M条道路，每行给出一对正整数，分别是该条道路直接连通的两个城镇的编号。为简单起见，城镇从1到N编号。 
       
注意:两个城市之间可以有多条道路相通,也就是说
       
3 3 
1 2 
1 2 
2 1 
这种输入也是合法的
       
当N为0时，输入结束，该用例不被处理。


输出描述:
对每个测试用例，在1行里输出最少还需要建设的道路数目。
示例1

输入

4 2
1 3
4 3
3 3
1 2
1 3
2 3
5 2
1 2
3 5
999 0
0

输出

1
0
2
998 <div style="font-family:Times New Roman;font-size:14px;background-color:F4FBFF;border:#B7CBFF 1px dashed;padding:6px"><div style="font-family:Arial;font-weight:bold;color:#7CA9ED;border-bottom:#B7CBFF 1px dashed"><i>Hint</i></div>Hint<i style="font-size:1px"></i> Huge input, scanf is recommended.

备注:
 Huge input, scanf is recommended.
算法知识视频讲解
添加回答
推荐
ShelterFromTheS头像 ShelterFromTheS 
#include <stdio.h>
int p[1222];
int i;
int find(int x)
{
    if(x!=p[x])
        p[x]=find(p[x]);
    return p[x];
}
int hebing(int x,int y)
{
    return p[x]=y;
}
int main()
{
    int n,m,x,y,x1,y1;
    while(~scanf("%d%d",&n,&m)&&n)
    {
        for(i=1;i<=1222;i++)
            p[i]=i;
        for(i=1;i<=m;i++)
        {
            scanf("%d%d",&x,&y);
            x1=find(x);
            y1=find(y);
            if(x1!=y1)
                hebing(x1,y1);
        }
        int ans=0;
        for(i=1;i<=n;i++)
        {
            if(p[i]==i)
                ans++;
        }
        printf("%d\n",ans-1);
    }
    return 0;
}
发表于 2015-10-28 15:18:03 回复(1)
蓝紫坊头像 蓝紫坊 
#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;
}

发表于 2018-10-19 16:38:37 回复(0)
C/C++
nbgao头像 nbgao 
#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;
}

发表于 2018-05-17 10:27:20 回复(0)
LiuTaw头像 LiuTaw
看了王道的机试指南来的，用并查集去做
#include<stdio.h>

#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;

}

发表于 2018-02-28 10:27:47 回复(0)
victorytein头像 victorytein
Huge input, scanf is recommanded...
用cin cout没有超时。。。

并查集问题，将所有相连接的节点构成一个集合。最后计算集合的个数，最终结果是集合的个数-1 
#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;
}

编辑于 2018-06-12 13:56:58 回复(0)
C/C++
F-L头像 F-L 
#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;
}

发表于 2018-03-28 12:49:59 回复(0)
reyne-d头像 reyne-d 
#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;
}

发表于 2018-03-04 10:15:01 回复(0)
牛客7464386号头像 牛客7464386号
#include<stdio.h>
#include<string.h>
int tree[1010];

int findroot(int x){
    if(tree[x]==-1)
        return x;
    int ret=findroot(tree[x]);
        tree[x]=ret;
    return ret;
}

int main(){
    int n,m,a,b;
    while(scanf("%d",&n),n!=0){
          scanf("%d",&m);    
    memset(tree,-1,sizeof(tree));
        while(m--!=0){
            scanf("%d%d",&a,&b);
                a=findroot(a);
                b=findroot(b);
            if(a!=b)
                tree[a]=b;
        }
    int ans=0;
    for(int i=1;i<=n;i++){
        if(tree[i]==-1)
            ans++;
    }
    printf("%d\n",ans-1);
} 
}
发表于 2018-02-18 17:30:17 回复(0)
Doooo头像 Doooo 
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];
    }

}

发表于 2016-04-14 10:26:57 回复(0)
提交观点

问题信息

难度：
9条回答 2189浏览

热门推荐

通过挑战的用户

查看代码

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号