Pagini recente » Cod sursa (job #2214141) | Clasament sada | Cod sursa (job #1097498) | Cod sursa (job #2209) | Cod sursa (job #1961291)
#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;
void DFS(std::vector<std::list<int>> edges, std::vector<int> &check, 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::list<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);
std::vector<std::list<int>> edges(V + 1);
std::vector<int> check(V + 1);
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 < edges.size(); i++) {
if (check[i] == 0) {
DFS(edges, check, i);
compCon++;
}
}
FILE *fout = fopen("dfs.out", "w");
fprintf(fout, "%d", compCon);
fclose(fout);
return 0;
}