某有名的群岛有N个岛屿，其中有些岛屿之间有桥（有的岛屿之间不止一座桥）可以相连，而有些岛屿之间是没有桥，则只能通过坐船来到达了。现在如果已经整个群岛的地图，请你求出最少坐船的次数。
Input:
有多组测试数据。每组测试数据以N和M开头，其中N（1<=N<=100）表示岛屿个数，M（1<=M<=100）表示桥的数量,接下来M行每行有两个整数A，B（1<=A,B<=N）,表示A岛屿和B岛屿有桥相连.
Output:
对于每组数据输出最少坐船次数.
Sample Input:
3 3
1 2
2 1
3 1
5 3
1 2
3 2
1 3
Sample Output:
0
2
//我采用向量作为堆储存每一块相连的岛屿（独立的岛屿单独储存）。
//向量的第一个元素若设为0则表明已移动到其他堆；若某一堆的元素个数不为一则将堆中每个元素代表的堆
//中的元素全部移动到元素所在堆中，一次递归，最终初始元素堆中的元素代表的就是相连岛屿的一块。算出向量第一个
//元素不为零的堆的个数就是相连岛屿块的个数，乘船的次数就是相连岛屿的块数减一。不知道这样的想法对不对，我
//初步实现了下，结果不正确。谁能给点建议
#include<iostream>
#include<vector>
using namespace std;
vector<int> island[101];//建立表示岛屿的向量
//=====================================
int move(int a,int b){//将b堆中的所有元素移到a堆
//如果b堆已经被移动或者只有一个元素则不移动
if(island[b][0] == 0)
return 0;
if(island[b].size()==1){
island[b][0] = 0;
return 0;
}
//如果b堆上还有其他元素，将其他元素对上的元素全部移到b堆
for(int i=1;i<island[b].size();i++)
move(island[b][0],island[b][i]);
//从1开始循环因为栈底元素无需压入
for(int i=1;i<island[b].size();i++)
island[a].push_back(island[b][i]);
island[b][0]= 0;//对已经移到其他堆的向量清零
}//-----------------------------------
int main(){
for(int i=1;i<101;i++)
island[i].push_back(i);//每个向量第一个元素为其序数
for(int n,m;cin>>n>>m;){
int num=0;
for(int i=0,a,b;i<m;i++){
cin>>a>>b;
a<b?island[a].push_back(b):island[b].push_back(a);//保持永远将较大的元素放到较小的元素表示的堆中
}
for(int j=1;j<n+1;j++){
int t = island[j].size();
if(t!=1 &&island[j][0]!=0){
for(int k=1;k<t;k++)
move(island[j][0],island[j][k]);
}
}
for(int i=1;i<n+1;i++)
if(island[i].size() != 0)
num++;
cout<<num-1<<endl;
}
}//=====================================
7 个解决方案
#1
应该就是dijkstra,只不过坐船的权值是1，有桥的权值是0。
#2
这道题就是求连接子图的个数 - 1
#3
题目贴得不全吧，什么情况下的最少坐船次数？遍历全部岛屿？
#4
ding
#5
是的
#6
是无向图吧？那就象2L说的，图中连通分量的个数-1就是最少乘船次数~
#7
这是简单的并查集
#1
应该就是dijkstra,只不过坐船的权值是1，有桥的权值是0。
#2
这道题就是求连接子图的个数 - 1
#3
题目贴得不全吧，什么情况下的最少坐船次数？遍历全部岛屿？
#4
ding
#5
是的
#6
是无向图吧？那就象2L说的，图中连通分量的个数-1就是最少乘船次数~
#7
这是简单的并查集