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