fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. int mark[110000];
  4. void dfs(vector<int> graph[],int num){
  5.     mark[num]=1;
  6.     for (int i=0; i<graph[num].size(); i++)
  7.         if (!mark[graph[num][i]]){
  8.             mark[graph[num][i]]=1;
  9.             dfs(graph,graph[num][i]);
  10.         }
  11. }
  12. int main(){
  13.     int t;
  14.     cin>>t;
  15.     while (t--){
  16.         int n,m,count=0;
  17.         cin>>n>>m;
  18.         vector<int> graph[n+1];
  19.         for (int i=0; i<m; i++){
  20.             int p,q;
  21.             cin>>p>>q;
  22.             graph[p].push_back(q);
  23.             graph[q].push_back(p);
  24.         }
  25.         memset(mark,0,sizeof(mark));
  26.         for (int i=1; i<=n; i++){
  27.             if (!mark[i]){
  28.                 ++count;
  29.                 dfs(graph,i);
  30.             }
  31.         }
  32.         cout<<count-1<<endl;
  33.     }
  34.     return 0;
  35. }
Success #stdin #stdout 0s 3708KB
comments (?)
stdin
copy 
1
8 5
1 2
2 3
4 5
5 6
7 8
stdout
copy 
2
https://ideone.com/2ikb00
language:
C++ (gcc 8.3)
created:
9 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!