Pagini recente » Cod sursa (job #361937) | Cod sursa (job #2335933) | Cod sursa (job #2411948) | Cod sursa (job #1346891) | Cod sursa (job #1961298)
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <ctime>
#include <deque>
#include <queue>
#include <stack>
#include <string>
#include <bitset>
#include <cstdio>
#include <limits>
#include <vector>
#include <climits>
#include <cstring>
#include <cstdlib>
#include <fstream>
#include <numeric>
#include <sstream>
#include <iostream>
#include <algorithm>
#include <unordered_map>
#include <stdlib.h>
#include <stdio.h>
using namespace std;
#define VMAX 100001
std::vector<int> edges[VMAX];
int check[VMAX];
void DFS(int v)
{
std::stack<int> stack_sim;
stack_sim.push(v);
check[v] = 1;
while (!stack_sim.empty()) {
int aux = stack_sim.top();
stack_sim.pop();
std::vector<int>::iterator it;
for (it = edges[aux].begin() ; it != edges[aux].end() ; it++) {
if (check[*it] == 0) {
stack_sim.push(*it);
check[*it] = 1;
}
}
}
}
int main()
{
int V, E, i;
int v1, v2;
int compCon = 0;
FILE *fd = fopen("dfs.in", "r");
fscanf(fd, "%d", &V);
fscanf(fd, "%d", &E);
for (i = 0; i < E; i++) {
fscanf(fd, "%d", &v1);
fscanf(fd, "%d", &v2);
edges[v1].push_back(v2);
edges[v2].push_back(v1);
}
fclose(fd);
for (i = 1; i <= V; i++) {
if (check[i] == 0) {
DFS(i);
compCon++;
}
}
FILE *fout = fopen("dfs.out", "w");
fprintf(fout, "%d", compCon);
fclose(fout);
return 0;
}