Pagini recente » Cod sursa (job #272422) | Cod sursa (job #2929146) | Cod sursa (job #1935101) | Cod sursa (job #476796) | Cod sursa (job #2797496)
#include <iostream>
#include <vector>
#include <queue>
#include <fstream>
#define N 100001
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
bool visited[N];
class Graph {
public:
vector <int> adiacenta[N];
void addEdge(int h, int t);
void DFS(int vf);
};
void Graph::addEdge(int h,int t)
{
adiacenta[h].push_back(t);
adiacenta[t].push_back(h);
}
void Graph::DFS(int vf)
{
visited[vf] = true;
for(int i = 0; i < adiacenta[vf].size(); ++i)
if (!visited[adiacenta[vf][i]])
DFS(adiacenta[vf][i]);
}
int main()
{
int n, m, n1, n2, conexe = 0;
fin >> n >> m;
Graph g;
for (int i = 1; i <= m; i++)
{
fin >> n1 >> n2;
g.addEdge(n1,n2);
}
for(int i = 1; i <= n; i++){
if (!visited[i])
{
conexe += 1;
g.DFS(i);
}
}
fout << conexe;
return 0;
}