Pagini recente » Cod sursa (job #1570619) | Cod sursa (job #1373847) | Cod sursa (job #2899146) | Cod sursa (job #1790152) | Cod sursa (job #1582948)
#include<fstream>
#include<stdlib.h>
#define NRMAXNXQ 100001
using namespace std;
FILE*in;
ofstream out("dfs.out");
long nr_nxq; // numarul de noduri
long nr_muchii; // numarul de muchii
long *LA[NRMAXNXQ];
long visited[NRMAXNXQ];
long nr_componente_conexe;
void read()
{
in=fopen("dfs.in", "r");
fscanf(in, "%ld%ld", &nr_nxq, &nr_muchii);
for (long i=1; i<=nr_nxq; i++)
{
LA[i]=(long *)realloc(LA[i], sizeof(long));
LA[i][0]=0;
}
for (long i=1; i<=nr_muchii; i++)
{
long x, y;
fscanf(in, "%ld%ld", &x, &y);
LA[x][0]++;
LA[x]=(long *)realloc(LA[x], (LA[x][0]+1)*sizeof(long));
LA[x][LA[x][0]]=y;
LA[y][0]++;
LA[y]=(long *)realloc(LA[y], (LA[y][0]+1)*sizeof(long));
LA[y][LA[y][0]]=x;
}
}
void DFS(int nxq)
{
visited[nxq]=nr_componente_conexe;
for (long i=1; i<=LA[nxq][0]; i++)
if (!visited[LA[nxq][i]])
DFS(LA[nxq][i]);
}
void solve()
{
for (long i=1; i<=nr_nxq; i++)
if (!visited[i])
{
nr_componente_conexe++;
DFS(i);
}
}
void show()
{
out<<nr_componente_conexe;
}
int main()
{
read();
solve();
show();
return 0;
}