Pagini recente » Cod sursa (job #1237748) | Cod sursa (job #2268632) | Cod sursa (job #923489) | Cod sursa (job #1514776) | Cod sursa (job #3204171)
#include <bits/stdc++.h>
#define SIZE 100005
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
//folosim STL vector
vector<int> Graph[ SIZE ];
int visited[SIZE],
N, //numarul de noduri
M, //numarul de muchii
componente_conexe; //componentele conexe
void DFS(int node) {
//marcam nodul ca fiind vizitat
visited[ node ] = 1;
for(int i = 0; i < Graph[ node ].size(); ++i) {
int descendent = Graph[ node ][ i ];
if(!visited[ descendent ])
DFS( descendent );
}
}
int main(int argc, char const *argv[]) {
fin>>N>>M;
int x, y;
//reprezentam graful in liste de adiacenta
for(int i = 0; i < M; ++i) {
fin>>x>>y;
Graph[x].push_back(y);
Graph[y].push_back(x);
}
for(int node = 1; node <= N; node++) {
if( !visited[ node ] ) {
componente_conexe++;
DFS( node );
}
}
//cout<<"Numarul de componente_conexe: "<<componente_conexe;
fout<<componente_conexe;
return 0;
}