Pagini recente » Cod sursa (job #1313494) | Cod sursa (job #2537351) | Cod sursa (job #1457826) | Cod sursa (job #1346715) | Cod sursa (job #1243482)
#include <cstdio>
#define Nmax 100050
using namespace std;
class element{
public:
element(){
inf = 0;
}
element(int x){
this->inf = x;
}
int inf;
};
class nod{
public:
nod(){
next = prev = NULL;
}
nod(element e,nod *next, nod *prev){
this->e = e;
this->next = next;
this->prev = prev;
}
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()){
Begin = End = new nod(e,0,0);
return;
}
End->next = new nod(e,0,End);
End = End->next;
}
void Push_front(element e){
if(Empty()){
Begin = End = new nod(e,0,0);
return;
}
Begin->prev = new nod(e,Begin,0);
Begin = Begin->prev;
}
void Insert(element e, nod *_crt)
{
nod *nodc = new nod(e,_crt,_crt->prev);
_crt->prev->next = nodc;
_crt->prev = nodc;
}
};
lista G[Nmax];
int N,M,used[Nmax];
void read()
{
scanf("%d%d",&N,&M);
int a,b;
for(int i = 1; i <= M; ++i){
scanf("%d%d",&a,&b);
G[a].Push_back(element(b));
G[b].Push_back(element(a));
}
}
void DFS(int k)
{
used[ k ] = 1;
for(nod *i = G[k].Begin; i; i = i->next)
if(!used[i->e.inf])
DFS(i->e.inf);
}
void solve()
{
int ncc = 0;
for(int i = 1; i <= N; ++i)
if(!used[i])
{
DFS(i);
++ncc;
}
printf("%d\n",ncc);
}
int main()
{
freopen("dfs.in","r",stdin);
freopen("dfs.out","w",stdout);
read();
solve();
return 0;
}