Pagini recente » Cod sursa (job #1427856) | Cod sursa (job #2114752) | Cod sursa (job #1630216) | Cod sursa (job #2076187) | Cod sursa (job #1016153)
#include <cstdio>
#include <cstdlib>
#define N 100001
using namespace std;
int n, m;
int *g[N], deg[N], v[N], mc[2*N][2];
void dfs(int x)
{
int *p;
v[x]=1;
for(p=g[x];*p!=-1;p++)
{
if(!v[*p])
{
dfs(*p);
}
}
}
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
int i, j;
long long sol=0;
scanf("%d%d", &n, &m);
for(i=1;i<=m;i++)
{
scanf("%d%d", &mc[i][0], &mc[i][1]);
deg[mc[i][0]]++;deg[mc[i][1]]++;
}
for(i=1;i<=n;i++)
{
g[i]=(int *) malloc((deg[i]+1)*sizeof(int));
g[i][deg[i]]=-1;
deg[i]=0;
}
for(;m;m--)
{
i=mc[m][0];j=mc[m][1];
//printf("%d %d\n", i, j);
g[i][deg[i]++]=j;
g[j][deg[j]++]=i;
}
for(i=1;i<=n;i++)
{
if(!v[i])
{
dfs(i);
sol++;
}
}
printf("%lld", sol);
}