Tunnels

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define fbo find_by_order
#define ook order_of_key

typedef long long ll;
typedef pair<ll,ll> ii;
typedef vector<int> vi;
typedef long double ld; 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> pbds;
typedef set<int>::iterator sit;
typedef map<int,int>::iterator mit;
typedef vector<int>::iterator vit;

set<int> adj[100001];
int head[100001];
int cnt;
void dfs(int u)
{
	if(adj[u].empty()) return ;
	int v = (*adj[u].begin());
	//cerr<<u<<' '<<v<<'\n';
	if(head[v]>0)
	{
		head[v]--;
		adj[u].erase(v);
		cnt--;
		return ;
	}
	adj[u].erase(v);
	dfs(v);
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	int n,m; cin>>n>>m;
	for(int i = 0; i < m; i++)
	{
		int u, v; cin>>u>>v; u--; v--;
		adj[u].insert(v);
	}
	cnt = 0;
	for(int i = 0; i < n; i++)
	{
		while(!adj[i].empty())
		{
			cnt++;
			dfs(i);
			head[i]++;
		}
	}
	cout<<cnt;
}

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