PATEST-A1013 题解

START:

太依赖vs了，结果没发现vs不支持对全局变量的检查，然后我函数里用的局部变量和全局变量名字重了，程序一直出错，我愣生生看了两个小时。
本篇为Hexo示例文档. # 这里是摘要部分,写1~2句话,就实现不全显示博文了..

题目

给一个图的邻接矩阵，并拿掉其中的一些点，求需要几条路，将其子图变成一个连通图。

想法

实质上不难，DFS 的循环每结束一次，就是寻找到一个通路——也就是一个连通块。用一个for循环遍历所有的顶点就 ok 了，而需要的路的数量就相当于连通块的个数 - 1。

代码

#include <iostream>
#include <cstring>

using namespace std;
int n, m, k;//城市总数，剩余高速路数，关注的城市数
int occ_city[2001];
bool vis[2001];

int map[1000][1000];
void dfs(int u, int p) 
{
	vis[u] = true;
	for (int i = 1; i <= n; i++)
	{
		if (i != p && vis[i]==false && map[u][i] != 0)
			dfs(i, p);
	}
}

int main()
{

	memset(vis, false, sizeof(vis));
	memset(map, 0, sizeof(map));
	cin >> n >> m >> k;
	for (int i = 0; i < m; i++)
	{
		int u, v;
		cin >> u >> v;
		map[u][v] = 1;
		map[v][u] = 1;
	}

	for (int i = 0; i < k; i++)
	{
		memset(vis, 0, sizeof(vis));
		int _cnt = 0,los;
		cin >> los;
		for (int j = 1; j <= n; j++)
		{
			if (j != los && vis[j] == false)
			{
				_cnt++;
				dfs(j, los);
			}
		}

		cout << _cnt-1<<endl;
	}

}

思考

在 DFS 函数的定义上，我将其定义为void dfs(int n, int p)而这与上面的全局变量int n重了，所以一直报错，让我差点崩了。（辣鸡vs不支持对全局变量检查，这一定不是我的问题！）

END