Pagini recente » Cod sursa (job #54816) | Cod sursa (job #2123887) | Cod sursa (job #2617851) | Cod sursa (job #1744931) | Cod sursa (job #904161)
Cod sursa(job #904161)
#include <iostream>
#include <fstream>
using namespace std;
#define MAX 100001
ifstream in("dfs.in");
ofstream out("dfs.out");
typedef struct nod
{
int vf;
nod *urm;
} *PNOD;
int N, M, viz[MAX], nr;
PNOD vec[MAX];
void adauga (PNOD &a, int b)
{
PNOD p = new nod;
p->vf = b;
p->urm = a;
a = p;
}
void citire ()
{
int x, y;
in>>N>>M;
for(int i = 1; i <= M; i++)
{
in>>x>>y;
adauga (vec[x], y);
adauga (vec[y], x);
}
}
void DFS (int x)
{
viz[x] = 1;
for(PNOD p = vec[x]; p; p = p->urm)
{
if(!viz[p->vf])
DFS (p->vf);
}
}
int compConexe()
{
for(int i = 1; i <= N; i++)
{
if(!viz[i])
{
nr++;
DFS (i);
}
}
return nr;
}
int main()
{
citire ();
out<<compConexe();
return 0;
}