Pagini recente » Rezultatele filtrării | Rezultatele filtrării | Rezultatele filtrării | Borderou de evaluare (job #1619916) | Cod sursa (job #2532078)
#include <iostream>
#include<fstream>
#include<stack>
#include<algorithm>
#include<vector>
using namespace std;
ifstream in("dfs.in");
ofstream out("dfs.out");
int n, m;
bool parcurs[100001];
vector<int>graf[100001];
void DFS(int nod){
stack<int>s;
s.push(nod);
while(!s.empty()){
int top = s.top();
s.pop();
if(parcurs[top] == false){
parcurs[top] = true;
for(int i = 0; i<graf[top].size(); ++i){
s.push(graf[top][i]);
}
}
}
}
int main()
{
int a, b;
while(in>>a>>b){
n = max(a, max(b, n));
graf[a].push_back(b);
}
int nr_componente = 0;
for(int i = 1; i<=n; ++i){
if(parcurs[i] == false){
++nr_componente;
DFS(i);
}
}
out<<nr_componente;
in.close();
out.close();
return 0;
}