Tunnels

//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()

void dfs (int x, const vvi &g, vector<char> &used, vi &comp)
{
    used[x] = 1;
    comp.pb(x);

    for (int dest : g[x])
    if (!used[dest])
        dfs(dest, g, used, comp);
}

void solve (int n)
{
    int m;
    cin >> m;
    vi in(n), out(n);
    vvi g(n);
    forn (i, m)
    {
        int x, y;
        cin >> x >> y;
        --x, --y;
        in[y]++;
        out[x]++;
        g[x].pb(y);
        g[y].pb(x);
    }

    int ans = 0;
    vector<char> used(n);
    forn (i, n) if (!used[i])
    {
        vi comp;
        dfs(i, g, used, comp);
        int cur = 0;
        for (int x : comp)
            cur += max(0, out[x] - in[x]);
        if (sz(comp) != 1)
            cur = max(cur, 1);
        ans += cur;
    }

    cout << ans << endl;
}

int main()
{
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "rt", stdin);
    //freopen("output.txt", "w", stdout);
    #endif // ONLINE_JUDGE

    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n;
    while (cin >> n)
        solve(n);
}

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

Test 11

Group: 3

Verdict: ACCEPTED

Test 12

Group: 3

Verdict: ACCEPTED

Test 13

Group: 3

Verdict: ACCEPTED

Test 14

Group: 3

Verdict: ACCEPTED

Test 15

Group: 3

Verdict: ACCEPTED