Pagini recente » Cod sursa (job #1570961) | Cod sursa (job #227499) | Cod sursa (job #637090) | Cod sursa (job #1111196) | Cod sursa (job #482810)
Cod sursa(job #482810)
#include <cstdio>
#include <vector>
#include <string>
using namespace std;
#define MAXN 100010
int main(){
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w", stdout);
vector <int> G[MAXN];
int d[MAXN], Stack[MAXN], v[MAXN], i, Si, aux, N, M, j, count;
memset(v, 0, sizeof(v));
memset(d, 0, sizeof(d));
scanf("%d%d", &N, &M);
for(i = 1; i <= M; i++){
scanf("%d%d", &aux, &j);
G[aux].push_back(j);
G[j].push_back(aux);
v[aux]++;
v[j]++;
}
count = 0;
for(aux = 1; aux <= N; aux++){
if(!d[aux]){
count++; Si=1; Stack[Si]=aux; d[aux]=1;
while(Si > 0){
i = Stack[Si];
Si--;
for(j = 0; j < v[i]; j++){
//printf("S:%d; V:%d; N:%d; J:%d\n", aux, v[i], G[i][j], j);
if(!d[G[i][j]]){
Stack[++Si]=G[i][j];
d[Stack[Si]]=1;
}
}
}
}
}
printf("%d\n", count);
return 0;
}