# Maximum Connected Graph using BFS and DFS

Oct 26th, 2020 (edited)
1,012
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
1. ***********************************************************************************
2. ************************************BFS********************************************
3. #include<bits/stdc++.h>
4. using  namespace  std;
5.
6. #define endl     "\n"
7. #define ll       long long
8. #define PI       acos(-1.0)
9. #define test     cout<<"\n****\n"
10. #define LCM(a,b) ((a/__gcd(a,b))*b)
11. #define READ(f)  freopen(f, "r", stdin)
12. #define WRITE(f) freopen(f, "w", stdout)
13. #define precise  fixed(cout);cout<<setprecision(20)
14. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
15.
16. const int N = 1000;
17. vector <int> graph[N];
18. bool visited[N];
19.
20. void BFS(int root){
21.
22.     visited[root] = true;
23.     queue<int> que;
24.     que.push(root);
25.
26.     while (!que.empty()){
27.
28.         int parent = que.front();
29.         que.pop();
30.
31.         for(int i=0;i<graph[parent].size();i++){
32.
33.             int child = graph[parent][i];
34.             if(!visited[child]) {
35.                 visited[child] = true;
36.                 que.push(child);
37.             }
38.         }
39.     }
40. }
41.
42. int main(){
43.
44.     int numNode,numEdge;
45.     cin>>numNode>>numEdge;
46.
47.     for(int i=0;i<numEdge;i++){
48.
49.         int node,edge;
50.         cin>>node>>edge;
51.         graph[node].push_back(edge);
52.         graph[edge].push_back(node);
53.     }
54.     int root;
55.     cin>>root;
56.     memset(visited, false,sizeof(visited));
57.
58.     int count = 0;
59.     for(int i=1;i<=numNode;i++){
60.         if(!visited[i]){
61.             count++;
62.             BFS(i);
63.         }
64.     }
65.     cout<<count<<endl;
66.
67.     return 0;
68. }
69.
70. ***********************************************************************************
71. ************************************DFS********************************************
72.
73. #include<bits/stdc++.h>
74. using  namespace  std;
75.
76. #define endl     "\n"
77. #define ll       long long
78. #define PI       acos(-1.0)
79. #define test     cout<<"\n****\n"
80. #define LCM(a,b) ((a/__gcd(a,b))*b)
81. #define READ(f)  freopen(f, "r", stdin)
82. #define WRITE(f) freopen(f, "w", stdout)
83. #define precise  fixed(cout);cout<<setprecision(20)
84. #define fast     ios_base :: sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
85.
86. const int N = 1000;
87. vector <int> graph[N];
88. bool visited[N];
89.
90. void DFS(int root){
91.
92.     if(visited[root]){
93.         return;
94.     }
95.
96.     visited[root] = true;
97.     for(int i=0;i<graph[root].size();i++){
98.         int child  = graph[root][i];
99.         if(!visited[child]){
100.             DFS(child);
101.         }
102.     }
103. }
104.
105. int main(){
106.
107.     int numNode,numEdge;
108.     cin>>numNode>>numEdge;
109.
110.     for(int i=0;i<numEdge;i++){
111.
112.         int node,edge;
113.         cin>>node>>edge;
114.         graph[node].push_back(edge);
115.         graph[edge].push_back(node);
116.     }
117.     int root;
118.     cin>>root;
119.     memset(visited, false,sizeof(visited));
120.
121.     int count = 0;
122.     for(int i=1;i<=numNode;i++){
123.         if(!visited[i]){
124.             count++;
125.             DFS(i);
126.         }
127.     }
128.     cout<<count<<endl;
129.
130.     return 0;
131. }
132.
133.
RAW Paste Data