Pagini recente » Cod sursa (job #1037985) | Cod sursa (job #1936396)
#include <cstdio>
#include <vector>
#define NMAX 100005
#include <stack>
using std::stack;
using std::vector;
void DFS(long node, bool viz[], vector <long> G[], stack <long> S){
S.push(node);
while(!S.empty()){
node = S.top();
S.pop();
if(viz[node] == false){
viz[node] = true;
for(int i{0};i < G[node].size();++i){
S.push(G[node][i]);
}
}
}
}
int main(){
freopen("dfs.in", "r", stdin);
freopen("dfs.out", "w",stdout);
long N, M;
std::vector <long> G[NMAX];
stack <long> S;
long x,y;
bool viz[NMAX];
scanf("%ld %ld ", &N, &M);
while(M--){
scanf("%ld %ld ", &x, &y);
G[x].push_back(y);
}
long nrc{0};
long i{0};
for(i = 1;i <= N;i++)viz[i] = false;
i = 1;
do{
DFS(i,viz,G,S);
nrc++;
while(i <= N && viz[i] == true)i++;
}while(i <= N);
printf("%ld\n", nrc);
return 0;
}