Pagini recente » Cod sursa (job #2845384) | Cod sursa (job #1141747) | Cod sursa (job #1404503) | Cod sursa (job #1148561) | Cod sursa (job #2929476)
#include <bits/stdc++.h>
using namespace std;
vector <int> G[100002];
vector <int> H[100002];
int n , m , x , y , S[100001] , D[100001] , c;
ifstream f("ctc.in");
ofstream g("ctc.out");
void dfs_succ(int v , int c)
{
S[v] = c;
for(int i : G[v])
if(!S[i]) dfs_succ(i , c);
}//in S retin succesorii fiecarui nod
void dfs_pred(int v , int c)
{
D[v] = c;
for(int i : H[v])
if(!D[i]) dfs_pred(i , c);
}//in D retin predecesorii fiecarui nod
int main()
{
f >> n >> m;
for(int i = 1 ; i <= m ; i++)
{
f >> x >> y;
G[x].push_back(y);
H[y].push_back(x);
}//
for(int i = 1 ; i <= n ; i++)
if(!S[i])
{
c++;
dfs_succ(i , c);
dfs_pred(i , c);
for(int i = 1 ; i <= n ; i++)
if(S[i] != D[i]) S[i] = D[i] = 0;
}
g << c;
}