Pagini recente » Cod sursa (job #2543844) | Cod sursa (job #265046) | Cod sursa (job #1097574) | Cod sursa (job #2137187) | Cod sursa (job #1244808)
#include <cstdio>
using namespace std;
class element{
public:
element(){ /// constructor care atribuie valoarea 0
this->inf = 0;
}
element(int x){
this->inf = x;
}
int inf;
};
class nod{
public:
nod(){
e.inf = 0;
next = prev = 0;
}
nod(element el, nod *p, nod *n){ /// constructor care imi da
this->next = n; /// relatia dintre vecini si element curent
this->prev = p;
this-> e = el;
}
element e;
nod *next,*prev;
};
class lista{
public:
lista(){
Begin = End = 0;
}
nod *Begin,*End;
bool Empty(){
if(End == 0)
return 1;
return 0;
}
void Push_back(element e){
if(Empty()){
nod *aux = new nod(e,0,0);
Begin = End = aux;
return;
}
nod *aux = new nod(e,End,0);
End->next = aux;
End = End->next;
}
void Push_front(element e){
if(Empty()){
nod *aux = new nod(e,0,0);
Begin = End = aux;
return;
}
nod * aux = new nod(e,0,Begin);
Begin->prev = aux;
Begin = Begin->prev;
}
void Pop_front(){
nod *aux = Begin;
Begin = Begin->next;
if(Begin)
Begin->prev = 0;
else
End = 0;
delete aux;
}
};
lista Graf[100005]; /// Graf[i] -> lista de vecini a nodului i
int viz[100005]; /// viz[i] -> daca am vizitat nodul
int N,M;
void read()
{
scanf("%d%d",&N,&M);
int a,b;
for(int i = 1; i <= M; ++i)
{
scanf("%d%d",&a,&b);
Graf[a].Push_back(element(b));
Graf[b].Push_back(element(a));
}
}
void DFS(int k){
viz[k] = 1;
for(nod *i = Graf[k].Begin; i; i = i->next)
if(!viz[i->e.inf])
DFS(i->e.inf);
}
void solve()
{
int ncc = 0;
for(int i = 1; i <= N; ++i)
if(!viz[i])
{
DFS(i);
++ncc;
}
printf("%d\n",ncc);
}
int main()
{
freopen("dfs.in","r",stdin); /// citim din lista.in
freopen("dfs.out","w",stdout);
read();
/**for(nod *i = Graf[1].Begin; i; i = i->next)
printf("%d ",i->e.inf);
*/
solve();
return 0;
}