题目描述
Problem Description
完美网络是连通网络的基础上要求去掉网络上任意一条线路，网络仍然是连通网络。求一个连通网络要至少增加多少条边可以成为完美网络。
Input
第一行输入一个数T代表测试数据个数（T<=20）。每个测试数据第一行2个数n,m 分别代表网络基站数和基站间线路数。基站的序号为从1到n。接下来m行两个数代表x,y 代表基站x,y间有一条线路。
(0 < n < m < 10000)
Output
对于每个样例输出最少增加多少线路可以成为完美网络。每行输出一个结果。
Sample Input
2
3 1
1 2
3 2
1 2
2 3
Sample Output
2
1
分析 & 代码
题目的要求很明确，连通网络的定义即去掉任意的一条边，整个网络仍然保持连通的网络，那么我们可以想到，对于这个网络来说，如果每个点的入度都为2或者2以上，就说明每个点至少有两条边连接到其他点上，这样删除一条边的话仍然也能保持连通，因此我们只要找到入度小于2的点然后在他们之间增加边，让他们的入度增加到2 这样就是最少添加的边数了，从这些入度小于2的点中拿出两个增加一条边，会有种Huffman树的感觉？同样可以使用优先队列的方式才储存这些点的信息：
#include<stdio.h>
#include<stdlib.h>
#include<memory.h>
#include<queue>
#include<algorithm>
#include<iostream>
using namespace std;
int indegree[10005];
int n,m;
int a,b;
int t;
int sum;
int main(){
cin>>t;
while(t--){
sum = 0;
memset(indegree, 0, sizeof(indegree)); //日常初始化
priority_queue<int, vector<int>, greater<int> > sav;
cin>>n>>m;
for(int i=0; i<m; i++){
cin>>a>>b;
indegree[a]++; // 无向图 两个点的度数都增加
indegree[b]++;
}
for(int i=1; i<=n; i++){
if(indegree[i] < 2)
sav.push(i);
}
while(sav.size() >= 2){ //注意这个地方结束条件 一种极端的情况是 点两两增加一条边之后最后剩下一个点 因此结束条件是 >=2
int tempa = sav.top(); //最后剩下一个的情况单独处理
sav.pop();
int tempb = sav.top();
sav.pop();
indegree[tempa]++;
indegree[tempb]++;
sum++;
if(indegree[tempa] < 2)
sav.push(tempa);
if(indegree[tempb] < 2)
sav.push(tempb);
}
if(!sav.empty()){ //此时 队列中度数<2的点不足两个 但是 队列不为空 说明还剩下一个点 直接加一 随便连一条边就好了
sum++;
}
cout<<sum<<endl;
}
}
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/116784.html
