Sunjaree

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