Advertisement
fooker

number of connected components

Apr 17th, 2023
214
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 0.77 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. int main(){
  5.     ll n,m;
  6.     cin>>n>>m;
  7.     vector<ll> adj[n+1];
  8.     bool visited[n+1] = {0};
  9.     for (ll i=1,x,y; i<=m; i++){
  10.         cin>>x>>y;
  11.         adj[x].push_back(y);
  12.         adj[y].push_back(x);
  13.     }
  14.     queue<ll> q;
  15.     ll ans=0;
  16.     for (ll i=1; i<=n; i++){
  17.         if (!visited[i]){
  18.             ans++;
  19.             visited[i]=true;
  20.             q.push(i);
  21.             while(!q.empty()){
  22.                 ll s=q.front();
  23.                 q.pop();
  24.                 for (auto u:adj[s]){
  25.                     if (visited[u]) continue;
  26.                     visited[u]=true;
  27.                     q.push(u);
  28.                 }
  29.             }
  30.         }
  31.     }
  32.     cout<<ans<<"\n";
  33.     return 0;
  34. }
  35.  
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement