HDU1232——通畅工程(并查集)

http://acm.hdu.edu.cn/showproblem.php?pid=1232

这道题是学习并查集的第一道题。

并查集,他的思路是构成一个树结构,如果这两个节点的根节点相同,那么说明这两个节点在一个集合里,否则不再一个集合。

查找根节点:当然是递归查找他上一层的父节点是什么。知道查找到的节点的父节点是他本身为止。

int find(int x) {
    return par[x] == x ? x : par[x] = find(par[x]);
}

将节点加入集合:为了方便查找,直接将节点连接到树的根节点上就可以了。

void unite(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    par[x]=y;

}

下面说一下题意:

这道题是希望所有点连通,那么就是希望所有点都在一个集合里。

所以最多的起始路径数应该是n-1(即所有点都连接到根节点上),根据已知的已经连接的路,如果在一个集合那么就返回,不再一个集合就把他们放在一个集合里,然后路径数减一。

#include<stdio.h>
int par[1001];
int ans;
int k,n,m,a,b;
int find(int x);
void unio(int x,int y);
int main(){
    while(~scanf("%d",&n)&&n!=0){
        scanf("%d",&m);
        for(int i=1;i<n+1;i++){
            par[i]=i;
        }
        k=n-1;
        for(int i=0;i<m;i++){
            scanf("%d%d",&a,&b);
           unio(a,b);
        }
        printf("%d\n",k);
    }
    return 0;
}
//两种查找根节点
int find(int x){
     while(par[x]!=x){
            x=par[x];
        }
        return x;
}
//int find(int x)
//{
//    return par[x]==x?x:(par[x]=find(par[x]));
//}
//联结两个点
void unio(int x,int y){
    x=find(x);
    y=find(y);
    if(x==y)return;
    k--;
    par[x]=y;

}
时间: 05-29

HDU1232——通畅工程(并查集)的相关文章

HDU1232 畅通工程 并查集

这道题跟HDU 1213 How Many Tables 并查集非常接近,都是赤裸裸的并查集的题. 思路:假设还需要建n-1条路,每并一次就自减1. 参考代码: #include<stdio.h> int fa[1000]; int find(int u) { return fa[u]==u?u:fa[u]=find(fa[u]); } int main() { int i,n,m,u,v,x,y; scanf("%d%d",&n,&m); while (n

B - 畅通工程(并查集)

对并查集理解之后就可以做这种题了,虽说这种题做的不多,这道题做过才这么快搞定,可是还是挺happy滴,加油 Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可).问最少还需要建设多少条道路? Input 测试输入包含若干测试用例.每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M:随后的M行对

nyoj608 畅通工程 并查集

//发现还是思想最重要 看懂了思想 代码就容易懂了.. #include <stdio.h> int fa[1005]; int find(int x) { if(fa[x]!=x) fa[x]=find(fa[x]); return fa[x]; } void comb(int a,int b) { fa[find(fa[a])]=find(fa[b]); } int main() { int n,m,a,b; while(scanf("%d",&n)&&

【HDU1232】畅通工程(并查集基础题)

裸敲并查集,很水一次AC 1 #include <iostream> 2 #include <cstring> 3 #include <cstdlib> 4 #include <cstdio> 5 #include <cctype> 6 #include <cmath> 7 #include <algorithm> 8 #include <numeric> 9 #include <string> 1

并查集基础 模板题 hdu1232 畅通工程

模板题 引入并查集——一则有趣的故事 为了解释并查集的原理,我将举一个更有趣的例子.话说江湖上散落着各式各样的大侠,有上千个之多.他们没有什么正当职业,整天背着剑在外面走来走去,碰到和自己不是一路人的,就免不了要打一架.但大侠们有一个优点就是讲义气,绝对不打自己的朋友.而且他们信奉“朋友的朋友就是我的朋友”,只要是能通过朋友关系串联起来的,不管拐了多少个弯,都认为是自己人.这样一来,江湖上就形成了一个一个的群落,通过两两之间的朋友关系串联起来.而不在同一个群落的人,无论如何都无法通过朋友关系连起

并查集-HDU1232

转的其他人的...不知道谁的... (⊙o⊙) 来看一个实例,杭电1232畅通工程 首先在地图上给你若干个城镇,这些城镇都可以看作点,然后告诉你哪些对城镇之间是有道路直接相连的.最后要解决的是整幅图的连通性问题.比如随意给你两个点,让你判断它们是否连通,或者问你整幅图一共有几个连通分支,也就是被分成了几个互相独立的块.像畅通工程这题,问还需要修几条路,实质就是求有几个连通分支.如果是1个连通分支,说明整幅图上的点都连起来了,不用再修路了:如果是2个连通分支,则只要再修1条路,从两个分支中各选一个

hdu 1232 畅通工程(并查集算法)

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1232 畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 31088    Accepted Submission(s): 16354 Problem Description 某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条

HDU 1232 畅通工程 (并查集)

某省调查城镇交通状况,得到现有城镇道路统计表,表中列出了每条道路直接连通的城镇.省政府“畅通工程”的目标是使全省任何两个城镇间都可以实现交通(但不一定有直接的道路相连,只要互相间接通过道路可达即可).问最少还需要建设多少条道路? Input测试输入包含若干测试用例.每个测试用例的第1行给出两个正整数,分别是城镇数目N ( < 1000 )和道路数目M:随后的M行对应M条道路,每行给出一对正整数,分别是该条道路直接连通的两个城镇的编号.为简单起见,城镇从1到N编号. 注意:两个城市之间可以有多条道

hdu 1233 还是畅通工程 kruskal最小生成树并查集实现

http://acm.hdu.edu.cn/showproblem.php?pid=1233 杭电ACM暑期集训队的选拔 还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)Total Submission(s): 30319    Accepted Submission(s): 13542 Problem Description 某省调查乡村交通状况,得到的统计表中列