Pagini recente » Cod sursa (job #2720810) | Cod sursa (job #1653632) | Cod sursa (job #65561) | Cod sursa (job #3174209) | Cod sursa (job #577969)
Cod sursa(job #577969)
#include <fstream>
#include <cstdio>
#include <cstdlib>
#define NMAX 100007
#define Input "dfs.in"
#define Output "dfs.out"
using namespace std;
bool viz[NMAX];
int N,M;
int* a[NMAX];
ofstream fout(Output);
inline void push(int e1,int e2)
{
a[e1]=(int*)realloc(a[e1],(++a[e1][0]+1)*sizeof(int));
a[e2]=(int*)realloc(a[e2],(++a[e2][0]+1)*sizeof(int));
a[e1][a[e1][0]]=e2;
a[e2][a[e2][0]]=e1;
}
inline void read()
{
ifstream fin(Input);
fin>>N>>M;
int i,e1,e2;
for(i=1; i<=N; i++)
a[i]=(int*)realloc(a[i],sizeof(int)) ,a[i][0]=0;
for(i=1; i<=M; i++)
fin>>e1>>e2,push(e1,e2);
}
inline void df(int nod)
{
viz[nod]=1;
int i;
for(i=1; i<=a[nod][0]; i++)
if(!viz[a[nod][i]])
df(a[nod][i]);
}
int main(){
int i,nrc=0;
read();
for(i=1; i<=N; i++)
if(!viz[i])
nrc++,df(i);
fout<<nrc<<'\n';
return 0;
}