Pagini recente » Cod sursa (job #479706) | Cod sursa (job #529923) | Cod sursa (job #2336523) | Cod sursa (job #1096523) | Cod sursa (job #1975338)
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <vector>
#include <queue>
#include <algorithm>
#define WHITE 0
#define BLACK 1
#define GREY 2
void dfs();
void explore(int node);
std::vector<std::vector<int>> graph;
std::vector<int> colors;
std::vector<int> distance;
int T = 0;
int number = 0;
int main() {
int N,M;
FILE *in = fopen("dfs.in","r");
FILE *out = fopen("dfs.out","w");
fscanf(in,"%d",&N);
fscanf(in,"%d",&M);
for(int i = 0; i < N; i++) {
std::vector<int> temp;
graph.push_back(temp);
distance.push_back(INT32_MAX);
}
for(int i = 0; i < M; i++) {
int start,end;
fscanf(in,"%d %d",&start,&end);
if(start != end) {
graph[start - 1].push_back(end - 1);
graph[end - 1].push_back(start - 1);
}
}
dfs();
fprintf(out,"%d",number);
fclose(in);
fclose(out);
return 0;
}
void dfs() {
for(int i = 0; i < graph.size(); i++) {
colors.push_back(WHITE);
}
T = 0;
for(int i = 0; i < graph.size(); i++) {
if( colors[i] == WHITE ) {
explore(i);
number++;
}
}
}
void explore(int node) {
distance[node] = T++;
colors[node] = GREY;
for(int neightbords : graph[node]) {
if (colors[neightbords] == WHITE) {
explore(neightbords);
}
}
colors[node] = BLACK;
T++;
}