Pagini recente » Cod sursa (job #2123417) | Cod sursa (job #2528487) | Cod sursa (job #2598568) | Cod sursa (job #2051953) | Cod sursa (job #743318)
Cod sursa(job #743318)
#include<fstream>
#define NMAX 100010
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
struct nod
{
int x;
nod *leg;
} *a[NMAX], *ultim[NMAX];
int n, m, nr[NMAX], vz[NMAX];
void Adauga(int x, int y)
{
nod *q;
++nr[x];
if (nr[x]==1)
{
a[x]=ultim[x]=new nod;
a[x]->leg=NULL; a[x]->x=y;
}
else
{
q=new nod; q->leg=NULL;
q->x=y;
ultim[x]->leg=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 *p;
vz[x]=1;
p=a[x];
while (p)
{
if (!vz[p->x]) DFS(p->x);
p=p->leg;
}
}
void Solve()
{
int i, nr=0;
for (i=1; i<=n; ++i)
if (!vz[i]) DFS(i), ++nr;
g<<nr<<"\n";
}
int main()
{
Citeste();
Solve();
f.close();
g.close();
return 0;
}