Pagini recente » Cod sursa (job #1021242) | Cod sursa (job #1616822) | Cod sursa (job #1156042) | Cod sursa (job #104161) | Cod sursa (job #2797459)
#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);
int k = 0;
int noduri_in_componente_conexe = 0;
void mark_unvisited(int poz);
int conexe();
};
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){
k++;
noduri_in_componente_conexe++;
// marked[*i] = k;
DFS(*i);
}
}
void Graph::mark_unvisited(int poz)
{
visited[poz] = false;
}
int Graph::conexe()
{
return k;
}
int main()
{
Graph g;
fin>>N>>M;
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)
{
g.DFS(i);
if(nr_comp_conexe == g.conexe())
{
g.mark_unvisited(i);
}
else
{
nr_comp_conexe = g.conexe();
}
}
//cout<<nr_comp_conexe;
int total_noduri_in_comp_conexe = g.noduri_in_componente_conexe + nr_comp_conexe;
// cout<<total_noduri_in_comp_conexe;
fout<<N - total_noduri_in_comp_conexe + nr_comp_conexe;
return 0;
}