Pagini recente » Cod sursa (job #2773993) | Cod sursa (job #3030773) | Cod sursa (job #866361) | Cod sursa (job #1191419) | Cod sursa (job #765675)
Cod sursa(job #765675)
#include<fstream>
#define NMAX 100010
using namespace std;
int n, m, vz[NMAX];
struct nod
{
int x;
nod* urm;
} *a[NMAX], *ultim[NMAX];
ifstream f("dfs.in");
ofstream g("dfs.out");
void Adauga(int x, int y)
{
nod *q;
if (a[x]==NULL)
{
a[x]=new nod;
a[x]->x=y; a[x]->urm=NULL;
ultim[x]=a[x];
}
else
{
q=new nod;
q->x=y; q->urm=NULL;
a[x]->urm=q;
ultim[x]=q;
}
}
void Citeste()
{
int i, x, y;
f>>n>>m;
for (i=1; i<=m; ++i)
{
f>>x>>y;
Adauga(x, y);
Adauga(y, x);
}
}
void DFS(int x)
{
nod *q;
vz[x]=1;
for (q=a[x]; q!=NULL; q=q->urm)
if (!vz[q->x]) DFS(q->x);
}
int numar_cc()
{
int nr=0, nod;
for (nod=1; nod<=n; ++nod)
if (!vz[nod])
{
++nr;
DFS(nod);
}
return nr;
}
int main()
{
Citeste();
g<<numar_cc()<<"\n";
f.close();
g.close();
return 0;
}