一、技术总结
- 这一题是考查图的知识,题目的意思要理解清楚,就是考查统计图中连通块的数量,也就是没有一个结点后。
- 怎么删除该结点,并且统计连通块的数量成为问题解决的关键,这里可以当访问到结点时,直接返回,或则跳过,这种操作就是相当于删除了该结点。
memset(inq, false, sizeof(inq));
这个是初始化标记数组,可以用于反复的遍历数组。
- 还有这次出现了一个比较简单的问题,就是在写for循环的嵌套时,同时使用了i变量,导致答案错误,这种问题一下又检查不出来,细心点。
二、参考代码
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1010;
vector<int> Adj[maxn];
bool inq[maxn];
int node;//need to delete node
void DFS(int v){
if(v == node) return;
inq[v] = true;
for(int i = 0; i < Adj[v].size(); i++){
int u = Adj[v][i];
if(inq[u] == false){
DFS(u);
}
}
}
int main(){
int n, m, k;
scanf("%d%d%d", &n, &m, &k);
int a, b;
for(int i = 1; i <= m; i++){
scanf("%d %d", &a, &b);
Adj[a].push_back(b), Adj[b].push_back(a);
}
for(int i = 0; i < k; i++){
scanf("%d", &node);
memset(inq, false, sizeof(inq));
int sum = 0;
for(int j = 1; j <= n; j++){
if(j != node && inq[j] == false){
DFS(j);
sum++;
}
}
printf("%d
", sum-1);
}
return 0;
}