Pagini recente » Cod sursa (job #143238) | Cod sursa (job #671195) | Cod sursa (job #2528328) | Cod sursa (job #569396) | Cod sursa (job #2259166)
#include <cstdio>
#include <cstdlib>
#define MaxN 100005
using namespace std;
int N, M, i, *A[MaxN];
bool Fq[MaxN];
int k=0;
void Citire();
void DFS(int i);
int main()
{
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
Citire();
return 0;
}
void Citire(){
scanf("%d%d", &N, &M);
for(i=1; i<=N; ++i){
A[i]=(int *)realloc(A[i], sizeof(int));
A[i][0]=0;
}
for(i=1; i<=M; i++){
int x, y;
scanf("%d%d", &x, &y);
A[x][0]++;
A[x]=(int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
A[y][0]++;
A[y]=(int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
A[x][A[x][0]]=y;
A[y][A[y][0]]=x;
}
for(i=1; i<=N; ++i){
if(!Fq[i]){
Fq[i]=1;
DFS(i);
k++;
}
}
printf("%d", k);
return;
}
void DFS(int i){
int j;
for(j=1; j<=N; ++j){
if(!Fq[A[i][j]]){
Fq[A[i][j]]=1;
DFS(A[i][j]);
}
}
return;
}