Cod sursa(job #3211104)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 8 martie 2024 15:42:52
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.1 kb
#include <iostream>
#include <fstream>
#include <math.h>
#include <bitset>
#include <unordered_map>
#include <algorithm>
#include <map>
#include <vector>
#include <stack>
#define infi 999999


using namespace std;

ifstream in("ctc.in");
ofstream out("ctc.out");

const int N = 1e5+1;

int n, m;

vector<int> v[N];
int viz[N], tin[N] , dp[N];
stack<int> S;
vector<vector<int>> sol;

int k = 0;

void visit(int nod , int father)
{
	viz[nod]++;
	tin[nod] = ++k;
	S.push(nod);
	for (auto& i : v[nod])
	{
			if (viz[i] == 0)
			{
				visit(i, nod);
				dp[nod] += dp[i];
			}
			else if (viz[i] == 1 && tin[nod] >= tin[i])
			{
				dp[i]--;
				dp[nod] ++;
			}
	}
	if (dp[nod] == 0)
	{
		vector<int> aux;
		while (S.top() != nod)
		{
			aux.push_back(S.top());
			S.pop();
		}
		aux.push_back(nod);
		S.pop();
		sol.push_back(aux);
	}

}

signed main()
{
	cin >> n >> m;
	for (int i = 1,a,b; i <= m; i++)
	{
		cin >> a >> b;
		v[a].push_back(b);
	}
	visit(1, -1);
	int sol = 0;
	for (int i = 1; i <= n; i++)
	{
		if (dp[i] == 0)
			sol++;
	}
	cout << sol;
}