fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector<int> adj_list[100];
  5. int visited[100];
  6.  
  7. void BFS(int start) {
  8.     visited[start] = 1;
  9.     queue<int> q;
  10.     q.push(start);
  11.  
  12.     while (!q.empty()) {
  13.         int currnode = q.front();
  14.         q.pop();
  15.  
  16.         for (int i = 0; i < adj_list[currnode].size(); i++) {
  17.             int child = adj_list[currnode][i];
  18.             if (visited[child] == 0) {
  19.                 q.push(child);
  20.                 visited[child] = 1;
  21.             }
  22.         }
  23.     }
  24. }
  25.  
  26. int main() {
  27.     int node, edge;
  28.     cin >> node >> edge;
  29.  
  30.     // Fix: Loop should run for edge times, not edge+1
  31.     for (int i = 0; i < edge; i++) {
  32.         int u, v;
  33.         cin >> u >> v;
  34.         adj_list[u].push_back(v);
  35.         adj_list[v].push_back(u); // undirected
  36.     }
  37.  
  38.     int components = 0;
  39.     for (int i = 1; i <= node; i++) {
  40.         if (visited[i] == 0) {
  41.             BFS(i);
  42.             components++;
  43.         }
  44.     }
  45.  
  46.     cout << "Total connected components: " << components << endl;
  47.  
  48.     return 0;
  49. }
  50.  
Success #stdin #stdout 0s 5304KB
comments (?)
stdin
copy 
6 3
1 2
3 4
5 6
stdout
copy 
Total connected components: 3
https://ideone.com/4UnWT1
language:
C++ (gcc 8.3)
created:
1 day ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!