Pagini recente » Cod sursa (job #1909987) | Cod sursa (job #1292724) | Cod sursa (job #2279211) | Cod sursa (job #1986192) | Cod sursa (job #3156972)
#include <iostream>
#include <fstream>
#include <vector>
#include <list>
#include <queue>
using namespace std;
list<pair<int,int>> * readEdges(int& n, int& m, ifstream & in){
//dynamically allocate a list of pairs
list<pair<int,int>> * E = new list<pair<int,int>>;
//read dimentions
in>>n>>m;
int x, y;
//read edges
while(in>>x>>y){
E->push_back(pair<int,int>(x,y));
}
//return the list
return E;
}
vector<list<int>> * edgesToList(list<pair<int,int>> * E, int n,bool directed){
//create a vector of lists
vector<list<int>> * L = new vector<list<int>>;
//set the vector's length to the number of nodes
L->resize(n);
//traverse the list of edges and add them to the adjacency lists
for(auto p : *E){
(*L)[p.first - 1].push_back(p.second);
if(!directed){
(*L)[p.second - 1].push_back(p.first);
}
}
//return the lists
return L;
}
void printList(vector<list<int>> * L){
for(int i = 0; i < (*L).size(); i++){
cout<<i + 1<<" : ";
for(auto p : (*L)[i]){
cout<<p<<" ";
}
cout<<endl;
}
}
void DFSInner(vector<list<int>> * L, int n, int current, bool * visited){
//"visit" the current node
visited[current - 1] = true;
//traverse the neighbours of the current node
for(auto x : (*L)[current - 1]){
if(!visited[x - 1]){
//visit the neighbour
visited[x - 1] = true;
DFSInner(L, n, x, visited);
}
}
}
int main(){
int n, m, nrComponente = 0;
ifstream f("dfs.in");
ofstream o("dfs.out");
list<pair<int, int>> * E = readEdges(n, m, f);
vector<list<int>> * L = edgesToList(E, n, false);
bool * visited = new bool[n];
for(int i = 0; i < n; i++){
visited[i] = false;
}
for(int i = 0; i < n; i++){
if(!visited[i]){
nrComponente ++;
DFSInner(L, n, i + 1, visited);
}
}
o<<nrComponente;
f.close();
o.close();
}