Pagini recente » Cod sursa (job #2204421) | Cod sursa (job #2747346) | Cod sursa (job #438911) | Cod sursa (job #2986149) | Cod sursa (job #2798002)
#include <bits/stdc++.h>
using namespace std;
ifstream fin( "dfs.in" );
ofstream fout( "dfs.out" );
class Graf{
private:
int N;
vector< vector<int> > adc;
vector<int> viz;
void Dfs(int nod);
public:
Graf(int n);
void AdaugaMuchie(int x, int y, int c);
int CompConexe();
};
void Graf :: Dfs(int nod) {
int i, w;
viz[nod] = 1;
for(i = 0; i < adc[nod].size(); i++) {
w = adc[nod][i];
if(viz[w] == 0)
Dfs(w);
}
}
Graf :: Graf(int n) {
N = n;
adc.resize( n + 1 );
viz.resize( n + 1 );
}
void Graf :: AdaugaMuchie(int x, int y, int c = 0) {
adc[x].push_back(y);
adc[y].push_back(x);
}
int Graf :: CompConexe() {
int i, conexe;
conexe = 0;
for(i = 1; i <= N; i++)
viz[i] = 0;
for(i = 1; i <= N; i++)
if( viz[i] == 0 ) {
Dfs( i );
++conexe;
}
return conexe;
}
int main()
{
int n, m , x, y, i;
fin>>n>>m;
Graf G(n);
for(i = 1; i <= m; i++) {
fin >> x >> y;
G.AdaugaMuchie( x, y);
}
fout << G.CompConexe();
return 0;
}