Pagini recente » Cod sursa (job #3180771) | Cod sursa (job #1171367) | Cod sursa (job #1769035) | Cod sursa (job #2112136) | Cod sursa (job #3219159)
#include <iostream>
#include <vector>
#define SIZE 100009
#define FIN "dfs.in"
#define FOUT "dfs.out"
#define pb push_back
using namespace std;
int N, //numarul de noduri
M; //numarul de muchii
vector<int> Graph[SIZE];//graph
int visited[SIZE],
compoments;
void read_graph() {
int x, y;
freopen(FIN, "r", stdin);
cin>>N>>M;
//cout<<N<<M;
for(int i = 1; i <= M; ++i) {
cin>>x>>y;
Graph[x].pb(y);
Graph[y].pb(x);
}
}
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 );
}
}
}
void find_components_connex() {
for(int node = 1; node <= N; node++) {
if(!visited[ node ]) {
compoments++;
DFS(node);
}
}
freopen(FOUT, "w", stdout);
//cout<<"Numarul de compomente conexe = "<<compoments;
cout<<compoments;
}
int main(int argc, char const *argv[]) {
read_graph();
find_components_connex();
return 0;
}