Tunnels

#include <iostream>
#include <algorithm>
#include <set>
using namespace std;
set <int> s[100002],v;
set <int>::iterator it;
int q[100002];
int n,m;
void dfs(int gag,int ngag){
    if(ngag!=gag){
        m--;
        it=s[ngag].lower_bound(gag);
        s[ngag].erase(it);
        q[gag]--;
        if(q[gag]==0)
            v.insert(gag);
    }
    if(s[gag].size()==0)
        return;
    int to=*(s[gag].begin());
    dfs(to,gag);
    return;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++)
        v.insert(i);
    for(int i=0;i<m;i++){
        int j,k;
        cin>>j>>k;
        s[j].insert(k);
        q[k]++;
        if(q[k]==1)
            v.erase(v.lower_bound(k));
    }
    int ans=0;
    while(m>0){
        ans++;
        while(1){
            int k=*(v.begin());
            if(s[k].size()==0)
                v.erase(v.begin());
            else
                break;
        }
        dfs(*v.begin(),*v.begin());
    }
    cout<<ans<<endl;
    return 0;
}

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