Pagini recente » Cod sursa (job #526726) | Cod sursa (job #1533667) | Cod sursa (job #1750841) | Cod sursa (job #2686030) | Cod sursa (job #1682166)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream f("dfs.in" );
ofstream g("dfs.out");
int NrNoduri, NrMuchii, x, y, compConex;
vector<int> vecini[100001];
bool visit[100001];
void BFS(int x) {
visit[x] = 1;
for ( vector<int>::iterator it = vecini[x].begin() ; it!=vecini[x].end() ; it++ )
BFS(*it);
}
int main() {
f >> NrNoduri >> NrMuchii;
for ( int i=1 ; i<=NrMuchii ; i++ ) {
f >> x >> y;
vecini[x].push_back(y);
}
for ( int i=1 ; i<=NrNoduri ; i++ )
if ( !visit[i] ) {
BFS(i);
compConex++;
}
g << compConex;
}