Pagini recente » Cod sursa (job #287959) | Cod sursa (job #1049423) | Cod sursa (job #10929) | Cod sursa (job #980981) | Cod sursa (job #3219188)
#include<iostream>
#include<vector>
#define SIZE 10000000
#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];
int visited[SIZE],
components;
void readGraph() {
int x, y;
freopen(FIN, "r", stdin);
cin>>N>>M;
for(int i=1; i<=M; ++i) {
cin>>x>>y;
Graph[x].pb(y);
Graph[y].pb(x);
}
}
void DFS(int node) {
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 ] ) {
components++;
DFS(node);
}
}
freopen(FOUT, "w", stdout);
cout<<components;
}
int main(int argc, char const *argv[])
{
readGraph();
find_components_connex();
}