Pagini recente » Cod sursa (job #352957) | Cod sursa (job #2286454) | Cod sursa (job #2830034) | Cod sursa (job #1049292) | Cod sursa (job #2301894)
#include <iostream>
#include <fstream>
#include <list>
using namespace std;
class Graph{
int n;
list<int> *edges;
public:
Graph(int n){
this->n=n;
this->edges = new list<int>[n];
};
void addEdge(int x,int y){
edges[x].push_back(y);
edges[y].push_back(x);
}
void DFS(int s,bool visited[]){
visited[s]=true;
for(list<int>::iterator i = edges[s].begin();i!=edges[s].end();i++){
if(!visited[*i]){
DFS(*i,visited);
}
}
}
};
int main()
{
ifstream f("dfs.in");
ofstream g("dfs.out");
int m,n,x,y,k(0);
f>>n>>m;
Graph *g = new Graph(n);
while(m--){
f>>x>>y;
g->addEdge(x,y);
}
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]){
++k;
g->DFS(i,visited);
}}
g<<k;
f.close();
g.close();
return 0;
}