Pagini recente » Cod sursa (job #338706) | Cod sursa (job #567314) | Cod sursa (job #2888223) | Cod sursa (job #1530759) | Cod sursa (job #1682180)
#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++ )
if ( !visit[*it] ) BFS(*it);
}
int main() {
f >> NrNoduri >> NrMuchii;
for ( int i=1 ; i<=NrMuchii ; i++ ) {
f >> x >> y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
for ( int i=1 ; i<=NrNoduri ; i++ )
if ( !visit[i] ) {
BFS(i);
compConex++;
}
g << compConex;
}