Pagini recente » Cod sursa (job #2451100) | Cod sursa (job #1827752) | Cod sursa (job #95822) | Cod sursa (job #2726610) | Cod sursa (job #2780162)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
const int NMAX = 100001;
class graf{
vector < int > Ad[NMAX];
int N;
public:
graf(int n):N(n){}
void addEdge(int x, int y){
Ad[x].push_back( y );
Ad[y].push_back( x );
}
void DFS( int nod, bool vis[] ){
vis[nod] = 1;
for( int i = 0; i < Ad[nod].size(); ++i ){
int w = Ad[nod][i];
if( vis[w] == 0 )DFS(w,vis);
}
}
int nrComponenteConexe(){
int nr = 0;
bool vis[NMAX] = {0};
for( int i = 1; i <= N; ++i )
if( vis[i] == 0 ){
DFS(i,vis);
nr++;
}
return nr;
}
};
int main()
{
int N, M, x, y;
fin >> N >> M;
graf G(N);
for( int i = 1; i <= M; ++i ){
fin >> x >> y;
G.addEdge(x,y);
}
fout << G.nrComponenteConexe() << '\n';
return 0;
}