Pagini recente » Cod sursa (job #534849) | Cod sursa (job #2366879) | Cod sursa (job #2233468) | Cod sursa (job #2227990) | Cod sursa (job #2782414)
#include <iostream>
using namespace std;
struct nod{
nod *next;
int val;
};
class Graph{
private:
nod *varfuri[100001];
int nrVarfuri;
int nrMuchii;
int varfStart;
bool vizitat[100001];
public:
Graph(){
for(int i = 0;i<100001;++i){
vizitat[i] = 0;
}
}
void citire(){
cin>>nrVarfuri>>nrMuchii;
for(int i = 1;i<=nrMuchii;++i){
int x, y;
cin>>x>>y;
nod *p = new nod;
p->val = x;
p->next = varfuri[y];
varfuri[y] = p;
p = new nod;
p->val = y;
p->next = varfuri[x];
varfuri[x] = p;
}
}
void afisare(){
for(int i = 1;i<=nrVarfuri;++i){
nod *p = varfuri[i];
while(p){
cout<<p->val<<" ";
p = p->next;
}
cout<<endl;
}
}
void dfs(int varf){
vizitat[varf] = 1;
nod *p = varfuri[varf];
while(p){
if(!vizitat[p->val]){
dfs(p->val);
}
p = p->next;
}
}
int nrComponenteConexe(){
int contor = 0;
for(int i = 1;i<=nrVarfuri;++i){
if(!vizitat[i]){
++contor;
dfs(i);
}
}
return contor;
}
};
int main()
{
Graph g;
g.citire();
//g.afisare();
cout<<g.nrComponenteConexe();
return 0;
}