Pagini recente » Cod sursa (job #2920585) | Cod sursa (job #2325433) | Cod sursa (job #1369778) | Cod sursa (job #1750825) | Cod sursa (job #205981)
Cod sursa(job #205981)
#include <stdio.h>
#include <stdlib.h>
int N,M;
int * A[100000];
void citire()
{
freopen("dfs.in","r",stdin);
scanf("%d %d",&N,&M);
for(int i = 0 ; i < N; ++i)
{
A[i] = (int*) malloc(sizeof(int));
A[i][0] = 0;
}
for(int i = 0 ; i < M; ++i)
{
int u,v;
scanf("%d %d",&u,&v);
A[u][0] ++;
A[u] = (int*) realloc(A[u], (A[u][0] + 1) * sizeof(int));
A[u][A[u][0]] = v;
}
}
bool vis[100000];
int nc;
void dfs(int i)
{
vis[i] = 1;
for(int j = 1; j <= A[i][0]; ++j)
dfs(A[i][j]);
}
void conex()
{
for(int i = 0 ; i < N; ++i)
if(!vis[i])
nc ++, dfs(i);
freopen("dfs.out","w",stdout);
printf("%d",nc);
}
int main()
{
citire();
conex();
return 0;
}