AtCoder Beginner Contest 284 C - Count Connected Components DFS的应用

Time Limit: 2 sec / Memory Limit: 1024 MB

Score : 300300 points

Problem Statement

You are given a simple undirected graph with NN vertices numbered 11 to NN and MM edges numbered 11 to MM. Edge ii connects vertex u_iui​ and vertex v_ivi​.
Find the number of connected components in this graph.

Notes

A simple undirected graph is a graph that is simple and has undirected edges.
A graph is simple if and only if it has no self-loop or multi-edge.

A subgraph of a graph is a graph formed from some of the vertices and edges of that graph.
A graph is connected if and only if one can travel between every pair of vertices via edges.
A connected component is a connected subgraph that is not part of any larger connected subgraph.

Sample Input 1 Copy

5 3
1 2
1 3
4 5

Sample Output 1 Copy

2

The given graph contains the following two connected components:

• a subgraph formed from vertices 11, 22, 33, and edges 11, 22;
• a subgraph formed from vertices 44, 55, and edge 33.

题目大意：求极大连通子图的连通分量，DFS图的遍历；
做法：创建一个无向图，图中存储每一行的行号能够到达的点。
如题目中给的样例，创建一个无向图
  1 2 3 4 5
1   2 3
2 1 
3 1 
4         5 
5       4 
这里我建议用二维向量，这样开辟的空间少，可以不用处理未被标记的点，然后dfs搜索每一层，下面附上代码；
1.用二维向量存储的：

1. #include <iostream>  
2. #include <bits/stdc++.h>  
3. #include <vector>  
4. using namespace std;  
5. const int N=150;  
6. int vex[N];//1已经访问，0，没有访问   
7. vector<int>a[N];  
8. void dfs(int x){//从x点开始   
9.     if(vex[x]==1)return;  
10.     vex[x]=1;  //标记已经访问
11.     for(int i=0;i<a[x].size();i++){  
12.         if(vex[a[x][i]]==0)dfs(a[x][i]);  //如果未访问过就从当前点搜当前点能够到达的点（深搜）
13.     }   
14. }   
15. int main()  
16. {  
17.     int n,m;  
18.     cin>>n>>m;  
19.     for(int i=0;i<m;i++){  
20.         int x,y;  
21.         cin>>x>>y;  
22.         a[x].push_back(y);  
23.         a[y].push_back(x);  
24.     }  
25.     int ans=0;  
26.     for(int i=1;i<=n;i++){  
27.         if(vex[i]==0){  
28.             dfs(i);  
29.             ans++;  
30.         }  
31.     }  
32.     cout<<ans<<endl;  
33.  }   

2.用数组存储的：

1. #include <bits/stdc++.h>  
2. #include <iostream>  
3. using namespace std;  
4. const int N=150;  
5. int vex[N];  
6. int mp[N][N];  
7. int n,m;  
8. void dfs(int x){  
9.     if(vex[x]==1)return;  
10.     vex[x]=1;  
11.     for(int i=1;i<=n;i++){  
12.         if(mp[x][i]!=0&&vex[mp[x][i]]==0)  
13.         dfs(mp[x][i]);  
14.     }  
15. }  
16. int main()  
17. {  
18.   
19.     cin>>n>>m;  
20.     for(int i=1;i<=n;i++){  
21.         for(int j=1;j<=n;j++){  
22.             mp[i][j]=0;  
23.         }  
24.     }  
25.     for(int i=0;i<m;i++){  
26.         int x,y;  
27.         cin>>x>>y;  
28.         mp[x][y]=y;  
29.         mp[y][x]=x;  
30.     }  
31. //  for(int i=1;i<=n;i++){  
32. //      for(int j=1;j<=n;j++){  
33. //          cout<<mp[i][j];  
34. //      }  
35. //      cout<<endl;  
36. //  }  
37.     int ans=0;  
38.     for(int i=1;i<=n;i++){  
39.         if(vex[i]==0){  
40.             ans++;  
41.             dfs(i);  
42.         }  
43.     }  
44.     cout<<ans<<endl;  
45.     return 0;  
46. }  

与AtCoder Beginner Contest 284的C题C - Ladder Takahashi 类似也是dfs深搜C - Ladder Takahashi (atcoder.jp)。