Pagini recente » Cod sursa (job #2731258) | Cod sursa (job #2208965) | Cod sursa (job #2767784) | Cod sursa (job #2705872) | Cod sursa (job #3250412)
#include <iostream>
#include <vector>
#include <fstream>
using namespace std;
/*
Se da un graf neorientat cu N noduri si M muchii.
Sa se determine numarul componentelor conexe ale grafului.
Fisierul de intrare dfs.in contine pe prima linie numerele N si M cu semnificatia din enunt, iar pe urmatoarele M linii se gasesc cate doua numere X si Y cu semnificatia: exista muchie de la nodul X la nodul Y.
*/
#define maxn 100010
ifstream f("dfs.in");
ofstream g("dfs.out");
bool viz[maxn];
void dfs(int nod, vector<vector<int>>& adiacernta){
viz[nod]=1;
for(auto urm: adiacernta[nod]){
if(!viz[urm]){
dfs(urm, adiacernta);
}
}
}
int main() {
int n,m,Start,cc=0,x,y;
f>>n>>m;
vector<vector<int>> Lista(n+1);
for(int i=1;i<=m;i++){
f>>x>>y;
Lista[x].push_back(y);
}
for(int i=1;i<=n;i++){
if(!viz[i]){
dfs(i,Lista);
cc++;
}
}
g<<cc;
}