Pagini recente » Cod sursa (job #1038983) | Cod sursa (job #1581411) | Cod sursa (job #1471434) | Cod sursa (job #2942341) | Cod sursa (job #2659797)
#include <iostream>
#include <fstream>
#include <list>
std::ifstream in("dfs.in");
std::ofstream out("dfs.out");
struct pair{
const int i,j;
pair (int a, int b) : i(a), j(b){}
};
class Graf{
std::list<int> * ad;
bool *vis;
int n;
int nr;
void DFS(int i);
public:
Graf(int n);
void addEdge(int i, int j);
int DFS();
};
Graf :: Graf(int n){
nr = 0;
this -> n = n;
vis = new bool[n+1];
for (int i = 1; i <= n; i ++)
vis[i] = false;
ad = new std::list<int> [n+1];
}
void Graf::addEdge(int i, int j){
ad[i].push_back(j);
ad[j].push_back(i);
}
int Graf::DFS(){
for (int i = 1; i <= n; i++)
if (! vis[i]){
nr ++;
DFS(i);
}
return nr;
}
void Graf::DFS(int i){
vis[i] = true;
std::list<int> :: iterator j;
for (j = ad[i].begin(); j != ad[i].end(); j ++)
if (!vis[*j]){
DFS(*j);
}
}
int main()
{
int n,m;
in >> n >> m;
Graf graf(n);
while (m){
int i, j;
in >> i >> j;
graf.addEdge(i,j);
m --;
}
out << graf.DFS();
out.close();
in.close();
return 0;
}