Tietoverkko

#include <bits/stdc++.h>
 
using namespace std;
 
set<pair<int, int> > nonEssential;
 
vector<int> conn[100000];
 
int origin[100000];
 
int n;
 
int vnum[100000];
 
int v = 0;
 
void markLoop(int a, int b){
 
//  cout << a << " " << b << endl;
 
  int k = a;
  int k2 = origin[k];
  while(b != k){
    if(k != k2)
      nonEssential.insert({min(k, k2), max(k, k2)});
    k = origin[k];
    k2 = origin[k];
  }
  nonEssential.insert({min(a, b), max(a, b)});
 
}
 
void setOrigin(int k){
  v++;
  for(int t : conn[k]){
    if(origin[t] == -1){
      origin[t] = k;
      vnum[t] = v;
      setOrigin(t);
    }else if(origin[k] != t && vnum[k] < vnum[t]){
      markLoop(t, k);
    }
  }
}
 
int main(){
  cin >> n;
  for(int i = 0; i < n; i++){
    int a, b;
    cin >> a >> b;
    a--; b--;
    conn[a].push_back(b);
    conn[b].push_back(a);
    origin[i] = -1;
  }
  origin[0] = 0;
  setOrigin(0);
  cout << n - nonEssential.size() << endl;
  /*for(pair<int, int> k: nonEssential){
    cout << k.first+1 << " | " << k.second+1 << endl;
  }*/ 
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: ACCEPTED

Test 3

Group: 1

Verdict: ACCEPTED

Test 4

Group: 1

Verdict: ACCEPTED

Test 5

Group: 1

Verdict: ACCEPTED

Test 6

Group: 2

Verdict: ACCEPTED

Test 7

Group: 2

Verdict: ACCEPTED

Test 8

Group: 2

Verdict: ACCEPTED

Test 9

Group: 2

Verdict: ACCEPTED

Test 10

Group: 2

Verdict: ACCEPTED