fork download
copy 
  1. #include<bits/stdc++.h> 
  2. using namespace std; 
  3. const int maxn = 1e5 +5; 
  4. int a[maxn], b[maxn], c[maxn]; 
  5. bool u[maxn]; 
  6.  
  7. int main(){ 
  8.  ios_base::sync_with_stdio(0); 
  9.  cin.tie(0); 
  10.  cout.tie(0); 
  11.  
  12.  int n; 
  13.  cin>>n; 
  14.  
  15.  map <int, int> m; 
  16.  set <int> s; 
  17.  
  18.  for(int i=1; i<=n; i++){ 
  19.   cin>>a[i]>>b[i]; 
  20.   m[a[i]]++; 
  21.   m[b[i]]++; 
  22.  } 
  23.  
  24.  for(int i=1; i<=n; i++){ 
  25.   int v1 = a[i], v2 = b[i]; 
  26.  
  27.   if(v1==v2){ 
  28.    c[i] = v1; 
  29.    u[v1] = 1; 
  30.   } 
  31.   else if(!u[v1] && u[v2]){ 
  32.    c[i] = v1; 
  33.    u[v1] = 1; 
  34.   } 
  35.   else if(u[v1] && !u[v2]){ 
  36.    c[i] = v2; 
  37.    u[v2] = 1; 
  38.   } 
  39.   else if(!u[v1] && !u[v2]){ 
  40.    /* 
  41.    4 4  
  42.    1 1 
  43.    2 5 
  44.    1 1 
  45.    */ 
  46.    int left1 = m[v1] - 1; 
  47.    int left2 = m[v2] - 1; 
  48.  
  49.    if(left1 < left2){ 
  50.     c[i] = v1; 
  51.     u[v1] = 1; 
  52.    } 
  53.    else{ 
  54.     c[i] = v2; 
  55.     u[v2] = 1; 
  56.    } 
  57.   } 
  58.      else{ 
  59.       c[i] = v1; 
  60.   } 
  61.  
  62.   m[v2]--; 
  63.   m[v1]--; 
  64.  
  65.   s.insert(c[i]); 
  66.  } 
  67.  
  68.  
  69.  cout<<s.size(); 
  70.  
  71. }
  72.  
Success #stdin #stdout 0.01s 5456KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/3mnoD2
language:
C++14 (gcc 8.3)
created:
2 years ago
visibility:
secret

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!