Pagini recente » Cod sursa (job #763148) | Cod sursa (job #2705760) | Cod sursa (job #2987020) | Cod sursa (job #1141030) | Cod sursa (job #3249775)
#include <iostream>
#include <list>
#include <stack>
#include <fstream>
using namespace std;
class Graph{
private:
int nVert;
int nEdg;
bool oriented;
list<int>* edges;
void dfsUtil(int start, bool* visited){
int current;
stack<int> toVis;
toVis.push(start);
while(toVis.size()){
current = toVis.top();
toVis.pop();
visited[current-1]=1;
for(const auto& it : edges[current-1]){
if(!visited[it-1]) toVis.push(it);
}
}
}
public:
Graph(int c_nVert, int c_nEdg, int c_oriented) : nVert(c_nVert), nEdg(c_nEdg), oriented(c_oriented){
edges = new list<int>[nVert];
int x,y;
for(int i = 0 ; i<nEdg; i++){
cin>>x>>y;
edges[x-1].push_back(y);
if(!oriented){
edges[y-1].push_back(x);
}
}
}
Graph(int c_nVert, int c_nEdg, int c_oriented, istream& f) : nVert(c_nVert), nEdg(c_nEdg), oriented(c_oriented){
edges = new list<int>[nVert];
int x,y;
for(int i = 0 ; i<nEdg; i++){
f>>x>>y;
edges[x-1].push_back(y);
if(!oriented){
edges[y-1].push_back(x);
}
}
}
bool existsEdge(int x, int y){
for(const auto& it : edges[x-1]){
if(it==y) return true;
}
return false;
}
void dfs(int start, ostream& g){
bool* visited = new bool[nVert]{0};
int current;
stack<int> toVis;
toVis.push(start);
while(toVis.size()){
current = toVis.top();
toVis.pop();
visited[current-1]=1;
g<<current<<" ";
for(const auto& it : edges[current-1]){
if(!visited[it-1]) toVis.push(it);
}
}
delete[] visited;
}
int nrConnected(){
bool* visited = new bool[nVert]{0};
int nr = 0;
for(int i=0;i<nVert;i++){
if(!visited[i]){
nr++;
dfsUtil(i+1, visited);
}
}
delete[] visited;
return nr;
}
~Graph(){
delete[] edges;
}
};
ifstream f("dfs.in");
ofstream g("dfs.out");
int main()
{
int n,m,o;
f>>n>>m;
Graph gr(n,m,0,f);
g<<gr.nrConnected();
return 0;
}