fork download
copy 
  1.  
  2. #include<bits/stdc++.h>
  3. using namespace std;
  4. void dfs(vector<vector<int>> adj,vector<bool> &vis,int i,int &cnt)
  5. {
  6.     cnt++;
  7.     vis[i]=true;
  8.     for(auto j:adj[i])
  9.     {
  10.         if(!vis[j])
  11.         {
  12.             dfs(adj,vis,j,cnt);
  13.         }
  14.     }
  15. }
  16.  
  17. int main()
  18. {
  19.     int t;cin>>t;
  20.     for(int i=1;i<=t;i++)
  21.     {
  22.         int n,m;cin>>n>>m;
  23.         vector<vector<int>> adj(n);
  24.         vector<bool> vis(n,false);
  25.         if(m==0)
  26.         {
  27. //            Case #x: y
  28.             cout<<"Case #"<<i<<": "<<2*(n-1)<<endl;
  29.             continue;
  30.         }
  31.         while(m--)
  32.         {
  33.             int a,b;cin>>a>>b;
  34.             a--;b--;
  35.             adj[a].push_back(b);
  36.             adj[b].push_back(a);
  37.         }
  38.         int ans=0;
  39.         for(int i=0;i<n;i++)
  40.         {
  41.             if(!vis[i])
  42.             {
  43.                 ans+=2;
  44.                 int cnt=0;
  45.                 dfs(adj,vis,i,cnt);
  46.                 cnt--;
  47.                 ans+=cnt;
  48.             }
  49.         }
  50.         ans-=2;//as we took 1 more
  51.         cout<<"Case #"<<i<<": "<<ans<<endl;
  52.     }
  53. }
  54.  
Success #stdin #stdout 0s 4432KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/orBaEF
language:
C++14 (gcc 8.3)
created:
4 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!