Pagini recente » Cod sursa (job #347591) | Cod sursa (job #66047) | Cod sursa (job #1785234) | Cod sursa (job #1154296) | Cod sursa (job #2788438)
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
ifstream in("DFS.in");
ofstream out("DFS.out");
int cnt = 0;
class graph{
int V;
list<int> *adj;
public:
graph(int V){
this -> V = V;
adj = new list<int>[V];
}
void add_edge(int v, int w){
adj[v].push_back(w);
adj[w].push_back(v);
}
void BFS(int start){
bool *visited = new bool[V];
for(int i = 0; i < V; i++){
visited[i] = false;
}
list<int> q;
visited[start] = true;
q.push_back(start);
while(!q.empty()){
start = q.front();
cout << start << " ";
q.pop_front();
for(auto it = adj[start].begin(); it != adj[start].end(); it++){
if(!visited[*it]){
visited[*it] = true;
q.push_back(*it);
}
}
}
}
void DFS(int start, bool visited[]){
visited[start] = true;
//cout << start << " ";
for(auto it = adj[start].begin(); it != adj[start].end(); it++){
if(!visited[*it]){
DFS(*it, visited);
}
}
}
void connectedComponents(){
bool *visited = new bool[V];
for(int v = 0; v < V; v++){
visited[v] = false;
}
for(int v = 0; v < V; v++){
if(!visited[v]){
DFS(v, visited);
cnt++;
}
}
delete[] visited;
}
};
int main()
{
int n, m;
in >> n >> m;
graph g(n);
for(int i = 0; i < m; i++){
int v, w;
in >> v >> w;
g.add_edge(v, w);
}
g.connectedComponents();
out << cnt;
return 0;
}