Tunnels

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
ll U[100005],A[100005];
ll root(ll x){
    if(U[x]==x) return x;
    ll r=root(U[x]);
    U[x]=r;
    return r;
}
void join(ll x,ll y){
    ll nx=root(x);
    ll ny=root(y);
    U[ny]=nx;
}
ll V[100005];
ll V2[100005];
ll M[100005];
int main()
{
    //ifstream cin("in.in");
    ll n,k,x,y;
    cin>>n>>k;
    for(ll i=0;i<=n;i++)U[i]=i;
    for(ll i=0;i<k;i++){
        cin>>x>>y;
        x--; y--;
        V[x]++;
        V2[y]++;
        join(x,y);
    }
    ll r=0;
    for(ll i=0;i<n;i++){
        ll a=V[i]-V2[i];
        if(a<0)a=0;
        A[i]=a;
        r=r+a;
    }
    //cout<<r<<"\n";
    for(ll i=0;i<n;i++){
        ll ro=root(i);
        if(M[ro]==0)M[ro]=1;
        if(A[i]>0)M[ro]=2;
        //cout<<ro<<" "<<M[ro]<<"\n";
    }
    for(ll i=0;i<n;i++){
        if(M[i]==1)r++;
        if(V[i]==0 and V2[i]==0)r--;
    }
    cout<<r;
}

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