Pagini recente » Cod sursa (job #3131563) | Cod sursa (job #446417) | Cod sursa (job #2268420) | Cod sursa (job #2926070) | Cod sursa (job #3211107)
#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");
#define cin in
#define cout 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;
}