Pagini recente » Cod sursa (job #1005139) | Cod sursa (job #120152) | Cod sursa (job #2428154) | Cod sursa (job #2182190) | Cod sursa (job #2045733)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
using namespace std;
class Graph{
int vertices;
vector<list<int> > adList;
public:
vector<int> visited;
Graph(int V);
void addEdge(int x, int y);
void DFS(int start);
};
Graph::Graph(int V){
this->vertices = V;
adList.resize(V + 1);
visited.resize(V + 1, 0);
}
void Graph::addEdge(int x, int y){
adList[x].push_back(y);
}
void Graph::DFS(int start){
this->visited[start] = 1;
list<int>::iterator i;
for(i = adList[start].begin(); i != adList[start].end(); i++)
if(this->visited[*i] == 0)
this->DFS(*i);
}
int main(){
int vertices, edges, x, y;
int conex_comp = 0;
ifstream f("dfs.in");
f >> vertices >> edges;
Graph my_gr(vertices);
for(int i = 0; i < edges; i++){
f >> x >> y;
my_gr.addEdge(x, y);
}
f.close();
for(int i = 1; i < vertices + 1; i++){
if(my_gr.visited[i] == 0){
conex_comp++;
my_gr.DFS(i);
}
}
ofstream g("dfs.out");
g << conex_comp;
g.close();
return 0;
}