Pagini recente » Cod sursa (job #2587594) | Cod sursa (job #2604471) | Cod sursa (job #3258086) | Cod sursa (job #2672448) | Cod sursa (job #1046787)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
std::ifstream fin("dfs.in");
std::ofstream fout("dfs.out");
std::vector<int> noduri[100002];
int n, m;
int visited[100002];
void citire()
{
fin>>n>>m;
int a, b;
for(int i = 0; i < m; i++)
{
fin>>a>>b;
if(a != b)
{
noduri[a].push_back(b);
}
}
// for(int i = 1; i <= n; i++)
// {
// visited[i] = -1;
// }
}
std::stack<int> indici;
void dfs(int nod)
{
indici.push(nod);
// std::cout<<nod<<' ';
visited[nod] = 1;
for(int i = 0; i < noduri[indici.top()].size(); i++)
{
if(!visited[noduri[indici.top()][i]])
{
visited[noduri[indici.top()][i]] = 1;
dfs(noduri[indici.top()][i]);
}
}
indici.pop();
}
void rezolvare()
{
int nr = 0;
for(int i = 1; i <= n; i++)
{
if(!visited[i])
{
dfs(i);
nr++;
}
}
fout<<nr<<'\n';
}
int main()
{
citire();
rezolvare();
// dfs(1);
// for(int i = 1; i <= n; i++)
// {
// std::cout<<visited[i]<<' ';
// }
return 0;
}