Pagini recente » Cod sursa (job #621198) | Cod sursa (job #2444695) | Cod sursa (job #1419022) | Cod sursa (job #994242) | Cod sursa (job #2797473)
#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);
}
void Graph::DFS(int v)
{
visited[v] = true;
// cout << v << " ";
list<int>::iterator i;
for (i = adj[v].begin(); i != adj[v].end(); ++i)
if (visited[*i] != true){
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);
}
int nr_comp_conexe = 0;
for(int i = 1; i <= N; ++i)
{
if(!g.visited[i]){
cnt++;
g.DFS(i);
}
}
fout<<cnt;
return 0;
}