Pagini recente » Cod sursa (job #2797459) | Cod sursa (job #1531359) | Cod sursa (job #703990) | Cod sursa (job #2732567) | Cod sursa (job #2797476)
#include <bits/stdc++.h>
#include <fstream>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
int N, M;
class Graph
{
public:
map<int, bool> visited;
map<int, list<int> > adj;
void addEdge(int v, int w);
void DFS(int v);
};
void Graph::addEdge(int v, int w)
{
adj[v].push_back(w);
adj[w].push_back(v);
}
void Graph::DFS(int v)
{
visited[v] = 1;
// cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (visited[*i] != 1){
DFS(*i);
}
}
int main()
{
Graph g;
fin>>N>>M;
int cnt = 0;
for(int i = 0; i < M; ++i){
int n1,n2;
fin>>n1>>n2;
g.addEdge(n1,n2);
}
for(int i = 1; i <= N; ++i)
{
if(!g.visited[i]){
cnt++;
g.DFS(i);
}
}
fout<<cnt;
return 0;
}