Pagini recente » Cod sursa (job #655700) | Cod sursa (job #933243) | Cod sursa (job #387581) | Cod sursa (job #3156304) | Cod sursa (job #1451783)
#include <iostream>
#include <vector>
#include <cstdio>
using namespace std;
class Graph {
private:
vector<int> *adjList;
int connected_components;
int size;
public:
Graph(int size) {
this->size = size;
adjList = new vector<int>[size + 2];
connected_components = 0;
}
~Graph() {
delete[] adjList;
}
void addEdge(int u, int v) {
adjList[u].push_back(v);
}
void DFS() {
bool *visited = new bool[this->size + 2];
for(int i = 1; i <= this->size; i++) {
visited[i] = false;
}
//cout << "DFS: " ;
for(int i = 1; i <= this->size; ++i) {
if(visited[i] == false) {
connected_components++;
DFS_helper(i,visited);
}
}
cout << endl << "COnexe: " << connected_components << endl;
}
void DFS_helper(int start_node,bool *visited) {
vector<int>::iterator it;
visited[start_node] = true;
//cout << start_node << " ";
for(it = adjList[start_node].begin(); it != adjList[start_node].end(); ++it) {
if(visited[*it] == false) {
DFS_helper(*it, visited);
}
}
}
int getConnectedComp() {
return this->connected_components;
}
};
int main(int argc, char const *argv[])
{
int N, M, x, y;
FILE *f, *out;
out = fopen("dfs.out", "w");
if((f = fopen("dfs.in", "r")) == NULL) {
fprintf(stderr, "Can't open file!\n");
return 0;
}
fscanf(f,"%d %d", &N, &M);
Graph g(N);
for(int i = 0; i < M; i++) {
fscanf(f, "%d %d", &x, &y);
g.addEdge(x,y);
}
g.DFS();
fprintf(out, "%d\n", g.getConnectedComp());
fclose(f);
fclose(out);
return 0;
}