fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. vector <int> adj[100001];
  5. int vis[100001];
  6.  
  7. void initialise(){
  8.   memset(vis,0,100001);
  9.   for (int i = 0; i < 100001; i++){
  10.    adj[i].clear();
  11.   }
  12. }
  13.  
  14. void addEdges(int u, int v){
  15.   adj[u].push_back(v);
  16.   adj[v].push_back(u);
  17. }
  18.  
  19. void dfs(int v){
  20.   vis[v] = 1;
  21.   for (auto child : adj[v]){
  22.     if (!vis[child]){
  23.       dfs(child);
  24.     }
  25.   }
  26. }
  27.  
  28. int main(){
  29.   int T; cin >> T;
  30.   while (T--){
  31.     int N,M;
  32.     cin >> N >> M;
  33.     while(M--){
  34.       int u,v;
  35.       cin >> u >> v;
  36.       addEdges(u,v);
  37.       int cc = 0;
  38.       for (int i=1; i<=N; i++){
  39.         if (vis[i] == 0){
  40.     			dfs(i), cc++;
  41.     		}
  42.       }
  43.       cout << cc <<"\n";
  44.       initialise();
  45.     }
  46.   }
  47. }
  48.  
Success #stdin #stdout 0s 6012KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/w6Qwux
language:
C++14 (gcc 8.3)
created:
3 years 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!