问题与解答
描述:
国家建设高铁网络,网络由一些连接城市的高铁线路构成。现有高铁建设情况可列为一张统计表,表中列出了每一条高铁线路直接连接的两个城市。国家的建设目标是全国每两个城市之间都可以实现高铁交通(但不一定有直接的高铁线路相连,只要能间接通过高铁线路可达即可)。问最少还要建设多少条高铁线路?
输入说明:
测试用例的第1行给出两个正整数,分别是城市数目N(<1000)和现有高铁线路数目M。随后的M行对应M条高铁线路,每行给出一对正整数,分别是该条高铁线路直接连接的两个城市的编号。为简单起见,城市从1到N编号。
输出说明:
在一行上输出最少还需要建设多少条高铁线路。
输入样例:
9 8
1 2
1 3
2 4
3 4
5 7
5 6
6 7
8 9
输出样例:
2
//高铁网络
//需要建设的高铁线路 == 连通分量数 - 1
#include<stdio.h>
#include<vector>
using namespace std;
#define MaxN 1000
vector<int> G[MaxN]; //邻接矩阵建立图G
int M, N; //城市数和已有的高铁线路数
int Connection = 0; //连通分量
void GreatG(vector<int> G[]); //建立图
int Vis[MaxN] = {false}; //DFS求连通分量数
void DFS(int u);
void DFSTrave();
int main(){
scanf("%d%d", &N,&M);
GreatG(G);
DFSTrave();
printf("%d", Connection-1);
}
void GreatG(vector<int> G[]){
int u,v,i;
for(i = 0; i < M; i++){
scanf("%d%d", &u, &v); //输入边
G[u].push_back(v); //无向图
G[v].push_back(u);
}
}
void DFSTrave(){
int u;
for(u = 1; u <= N; u++){
if(Vis[u] == false){
DFS(u);
Connection++;
}
}
}
void DFS(int u){
Vis[u] = true;
int v,i;
for(i = 0; i < G[u].size(); i++){
v = G[u][i];
if(Vis[v] == false){
DFS(v);
}
}
}
题后反思
要让整个图连通,只需要让连通分量间连通。