Cod sursa(job #913672)
#include <fstream>
#include <stdlib.h>
using namespace std;
typedef struct s_nod
{
int info;
s_nod *next;
} nod;
ifstream f("dfs.in");
ofstream g("dfs.out");
int n,i,m,a,b,c=0;
nod *graf[100000];
bool exista[100000];
void verificare(int k)
{
nod *index2;
if (graf[k])
{
index2 = graf[k];
if (!exista[k])
{
exista[k]=true;
while(index2)
{
verificare(index2->info);
index2=index2->next;
}
}
}
else
exista[k]=true;
}
void dfs()
{
for (i=0; i<n; i++)
{
if (!exista[i])
{
c++;
verificare(i);
}
}
}
int main()
{
nod *index;
f >> n >> m;
for (i=0; i<m; i++)
{
f >> a >> b;
index = (nod*) malloc (sizeof(nod));
if(!index) return 0;
index->info = a;
index->next= graf[b];
graf[b]=index;
index = (nod*) malloc (sizeof(nod));
if(!index) return 0;
index->info= b;
index->next = graf[a];
graf[a]=index;
}
dfs();
g << c;
g.close();
return 0;
}