Pagini recente » Cod sursa (job #1128823) | Cod sursa (job #821100) | Cod sursa (job #1825023) | Cod sursa (job #1241973) | Cod sursa (job #238785)
Cod sursa(job #238785)
#include <cstdio>
#define N 100050
#define FIN "dfs.in"
#define FOUT "dfs.out"
int *a[N];
int x[N],y[N],d[N],n,m,viz[N],rez;
void read()
{
int i;
freopen(FIN,"r",stdin);
scanf("%d%d",&n,&m);
for (i=1;i<=m;++i)
{
scanf("%d%d",&x[i],&y[i]);
++d[x[i]];
++d[y[i]];
}
for (i=1;i<=n;++i)
{
a[i]=new int[d[i]++];
a[i][0]=0;
}
for (i=1;i<=m;++i)
{
a[x[i]][++a[x[i]][0]]=y[i];
a[y[i]][++a[y[i]][0]]=x[i];
}
}
void df(int x)
{
int i;
viz[x]=1;
for (i=1;i<=a[x][0];++i)
if (!viz[a[x][i]])
df(a[x][i]);
}
void solve()
{
int i;
for (i=1;i<=n;++i)
if (!viz[i])
{
df(i);
++rez;
}
}
void write()
{
freopen(FOUT,"w",stdout);
printf("%d\n",rez);
}
int main()
{
read();
solve();
write();
}