Pagini recente » Cod sursa (job #2633865) | Cod sursa (job #2775519) | Cod sursa (job #2754204) | Cod sursa (job #1311632) | Cod sursa (job #2780696)
//Parcurgere DFS - componente conexe
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int n, m;
int vizitat[100001];
vector<pair<int, int>> vm;
void dfs(int i)
{
vizitat[i] = 1;
for(int j=0; j<m; ++j) {
if (vm[j].first == i && vizitat[vm[j].second] == 0)
dfs(vm[j].second);
}
}
int main() {
int conexe=0;
fin>>n>>m;
for(int i=0; i<m; ++i)
{
int x ,y;
fin >> x >> y;
vm.push_back(make_pair(x, y));
}
for(int i=1; i<=n; ++i)
if(vizitat[i]!=1)
{
conexe++;
dfs(i);
}
fout<<conexe;
}