Pagini recente » Cod sursa (job #589466) | Cod sursa (job #572592) | Cod sursa (job #2111424) | Cod sursa (job #2065035) | Cod sursa (job #675743)
Cod sursa(job #675743)
#include <cstdio>
#include <algorithm>
#include <vector>
#define MAXN 100001
using namespace std;
int n, m;
vector<int> g[ MAXN ];
bool vizitat[ MAXN ];
void read()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
scanf("%d%d", &n, &m);
int u, v;
for(int i = 1; i <= n; ++i)
g[i].push_back(0);
for(int i = 1; i <= m; ++i)
{
scanf("%d%d", &u, &v);
g[ u ].push_back( v );
}
}
void dfs(int u)
{
vizitat[u] = true;
for(size_t i = 1; i <= g[ u ].size(); ++i)
if( !vizitat[ g[ u ][ i ] ] )
dfs(g[ u ][ i ]);
}
void solve()
{
int componenteConexe = 0;
for(int i = 1; i <= n; ++i)
if( !vizitat[i] )
{
dfs(i);
++componenteConexe;
}
printf("%d\n", componenteConexe);
}
int main()
{
read();
solve();
return 0;
}