题目描述
实际上是并查集的一钟运用,将每一个地点看作端点,然后合并集合,最后路径数目就是集合数目减去1
include[HTML_REMOVED]
const int INF = 10000;
using namespace std;
int n,m;
int a[INF];
int res;
int find(int x){
if(x == a[x]) return x;
else return a[x] = find(a[x]);
}
int main(){
//初始化并查集
for(int i = 0; i < INF; i){
a[i] = i;
}
cin>>n>>m;
int x, y;
for(int i = 0; i < m; i){
cin>>x>>y;
int t1 = find(x), t2 = find(y);
a[t2] = t1;//将右端点合并到左端点
}
//查看有多少个并查集
for(int i = 1; i <= n; i){
if(i == find(i))res;
}
cout<<res-1;
return 0;
}
样例
blablabla
算法1
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla
算法2
(暴力枚举) $O(n^2)$
blablabla
时间复杂度
参考文献
C++ 代码
blablabla