这个题。用dfs来计算，去除特定节点后的连通分量个数。我本来想，去除某节点，要把节点删掉，且把对应边全删掉，这样改动太大了，很麻烦，而且每次还得复原，看了别人的做法，其实每次把那个特定节点记为被访问过就好。这个题用cin,cout绝对超时，得用scanf,printf。其实dfs还是很简单的，不过邓书上的描述给我吓怕了，一直没想着总结，别人的dfs都很简单。其实是照着别人的代码和思路敲的，还是太菜了，由于建图的方式和别人不一样，照着别人的方式写dfs，没法得出答案，找bug找了好久，才把问题锁定在dfs里面，真的菜。11~13行，用我的建图方式应该是如代码所示用Edge[v][i]来访问邻居而不是直接i。我好菜啊，这题不难吧。哎，不断学习吧，今天也不是没有收获。dfs以后也能上手了。之前看邓书，邓老师喜欢把函数或者各种图封装在类里，我以前觉得实际敲代码不写在类里面（实际上可以），而是在main函数外写一个个函数，而我以前只会把变量声明定义在main函数里面，这就造成在main外定义的函数得传递好多个形参，返回值也不好弄，很麻烦，今天看别人的代码才突然意识到可以定义在全局变量里，这样就可以像类里面定义的函数一样形参比较少，也可以更改不在形参里面的参数。可能c++和c相比，c++的优势仅仅在于STL?类的作用不大。还遗留一个问题：
在全局变量里定义int N,在main函数里也可以定义int N，编译能通过，但是这两个N不是同一个东西，main函数里对N的赋值不能传递给全局变量N.有时间查查为什么.
1 #include<iostream> 2 #include<vector> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int visited[1001]; 7 vector<vector<int> > Edge(1001); 8 void DFS(int v) 9 { 10 visited[v]=1; 11 for(int i=0;i<Edge[v].size();i++) 12 if(visited[Edge[v][i]]==0) 13 DFS(Edge[v][i]); 14 15 } 16 int main(){ 17 int node[1001]; 18 int N,M,K,C1,C2; 19 scanf("%d%d%d",&N,&M,&K); 20 for(int i=0;i<M;i++) 21 { 22 scanf("%d%d",&C1,&C2); 23 Edge[C1].push_back(C2); 24 Edge[C2].push_back(C1); 25 } 26 int num,count=0; 27 for(int i=0;i<K;i++) 28 { 29 scanf("%d",&num); 30 visited[num]=1; 31 for(int j=1;j<=N;j++) 32 { 33 if(visited[j]==0) 34 { DFS(j); 35 count++; 36 } 37 } 38 printf("%d\n",count-1); 39 count=0; 40 fill(visited,visited+1001,0); 41 } 42 43 44 return 0; 45 }
原文：https://www.cnblogs.com/wsshub/p/12490206.html