算法训练22

1. 知识点总结

被第一题的第一个测试点狠狠的整emo了，呜呜呜~

2. 分题题解

1013

考察建模能力，即“去掉一个点之后，原图中连通图的个数-1”即为答案

第一版：22/25

#include<bits/stdc++.h>
using namespace std;
int N,M,K;
int id;
int u,v;
vector<vector<int> >graph;
vector<int>vis;
void bfs(int bg,int fobidden,int index){
	//开始位置，禁止访问结点，标记访问记号
	queue<int>q;
	q.push(bg);
	vis[bg]=index;
	while(!q.empty()){
		int top=q.front();
		q.pop();
		for(int i=0;i<graph[top].size();i++){
			if(graph[top][i]!=fobidden&&vis[graph[top][i]]!=index){
				q.push(graph[top][i]);
				vis[graph[top][i]]=index;
			}
		}
	} 
}
int Count(int id,int index){
	//计算id编号的城市陷落之后，需要修补的道路个数
	//即断掉了某一个结点之后，图中有cnt个连通图，返回cnt-1即需要修复个数 
	int cnt=0;
	for(int i=0;i<graph[id].size();i++){
		if(graph[id][i]!=id&&vis[graph[id][i]]!=index){
			//当前没访问过
			cnt++;
			bfs(graph[id][i],id,index) ;
		}
	}
	return cnt;
}
//对于每一个城市，如果陷落，需要弥补的高速公路的个数 
int main(){
	scanf("%d%d%d",&N,&M,&K); 
	graph.resize(N+1);
	vis.resize(N+1);
	fill(vis.begin(),vis.end(),-1);
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	//查询结果
	int ans;
	for(int i=0;i<K;i++){
		scanf("%d",&id);
		ans=Count(id,i);
		if(ans==0){
			printf("%d\n",ans);
		}else{
			printf("%d\n",ans-1);
		}
	} 
	return 0;
}

有一个测试点过不去是因为，题目给的初始化的地图并没有保证是一个连通图，所以改写如下AC：

#include<bits/stdc++.h>
using namespace std;
int N,M,K;
int id;
int u,v;
vector<vector<int> >graph;
vector<int>vis;
void bfs(int bg,int fobidden,int index){
	//开始位置，禁止访问结点，标记访问记号
	queue<int>q;
	q.push(bg);
	vis[bg]=index;
	while(!q.empty()){
		int top=q.front();
		q.pop();
		for(int i=0;i<graph[top].size();i++){
			if(graph[top][i]!=fobidden&&vis[graph[top][i]]!=index){
				q.push(graph[top][i]);
				vis[graph[top][i]]=index;
			}
		}
	} 
}
int Count(int id,int index){
	//计算id编号的城市陷落之后，需要修补的道路个数
	//即断掉了某一个结点之后，图中有cnt个连通图，返回cnt-1即需要修复个数 
	int cnt=0;
//	for(int i=0;i<graph[id].size();i++){
//		if(graph[id][i]!=id&&vis[graph[id][i]]!=index){
//			//当前没访问过
//			cnt++;
//			bfs(graph[id][i],id,index) ;
//		}
//	}
    //改写的部分
	for(int i=1;i<=N;i++){
		if(i!=id&&vis[i]!=index){
			cnt++;
			bfs(i,id,index);
		}
	}
	return cnt;
}
//对于每一个城市，如果陷落，需要弥补的高速公路的个数 
int main(){
	scanf("%d%d%d",&N,&M,&K); 
	graph.resize(N+1);
	vis.resize(N+1);
	fill(vis.begin(),vis.end(),-1);
	for(int i=0;i<M;i++){
		scanf("%d%d",&u,&v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
	//查询结果
	int ans;
	for(int i=0;i<K;i++){
		scanf("%d",&id);
		ans=Count(id,i);
		if(ans==0){
			printf("%d\n",ans);
		}else{
			printf("%d\n",ans-1);
		}
	} 
	return 0;
}

3. 参考资料