Tunnels

#include <iostream>
#include <stdlib.h>
 
const int MAX_ROOM = 100005;
 
using namespace std;
 
int depc [MAX_ROOM], arrc [MAX_ROOM], root [MAX_ROOM], ans [MAX_ROOM];
 
int find (int u) {
  if (root[u] == u) {
    return u;
  } else {
    root[u] = find(root[u]);
    return root[u];
  }
}
 
void merge (int u, int v) {
  if (find(u) != find(v)) {
    if (rand() % 2 == 0) {
      root[find(u)] = find(v);
    } else {
      root[find(v)] = find(u);
    }
  }
}
 
int main () {
  for (int i = 0; i < MAX_ROOM; i++) {
    root[i] = i;
  }
  
  int roomc, edgec;
  cin >> roomc >> edgec;
 
  for (int i = 0; i < edgec; i++) {
    int u, v;
    cin >> u >> v;
  
    depc[u]++;
    arrc[v]++;
 
    merge(u, v);
  }
 
  for (int i = 1; i <= roomc; i++) {
    if (depc[i] > arrc[i]) {
      ans[find(i)] += depc[i] - arrc[i];
    }
  }
 
  int sol = 0;
  for (int i = 1; i <= roomc; i++) {
    if (root[i] == i) {
      sol += max(ans[i], 1);
    }
  }
 
  cout << sol << endl;
}

Test 1

Group: 1

Verdict: ACCEPTED

Test 2

Group: 1

Verdict: WRONG ANSWER

Test 3

Group: 1

Verdict: WRONG ANSWER

Test 4

Group: 1

Verdict: WRONG ANSWER

Test 5

Group: 1

Verdict: WRONG ANSWER

Test 6

Group: 2

Verdict: WRONG ANSWER

Test 7

Group: 2

Verdict: WRONG ANSWER

Test 8

Group: 2

Verdict: WRONG ANSWER

Test 9

Group: 2

Verdict: WRONG ANSWER

Test 10

Group: 2

Verdict: WRONG ANSWER

Test 11

Group: 3

Verdict: WRONG ANSWER

Test 12

Group: 3

Verdict: WRONG ANSWER

Test 13

Group: 3

Verdict: WRONG ANSWER

Test 14

Group: 3

Verdict: WRONG ANSWER

Test 15

Group: 3

Verdict: WRONG ANSWER