Pagini recente » Cod sursa (job #1111173) | Cod sursa (job #2708806) | Cod sursa (job #2683185) | Cod sursa (job #56880) | Cod sursa (job #2782908)
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>
using namespace std;
class graf{
int noduri, muchii;
vector<vector<int>> adiacenta;
public:
graf(vector<vector<int>> a, int b, int c): adiacenta(a), noduri(b), muchii(c) {};
vector<int> bfs(int start){
vector<int> res(this->adiacenta.size(), -1);
vector<int> vis(this->adiacenta.size());
queue<int> q;
vis[start] = 1;
q.push(start);
res[start] = 0;
while(!q.empty()){
int curr = q.front();
q.pop();
for(int i:adiacenta[curr]){
if(vis[i] == 0){
vis[i] = 1;
q.push(i);
res[i] = res[curr]+1;
}
}
}
return res;
}
int dfs(){
vector<int> vis(this->noduri);
int res = 0;
stack<int> s;
for(int i=0; i<this->noduri; i++){
if(vis[i] == 0){
res++;
vis[i]=1;
s.push(i);
while(!s.empty()){
int curr = s.top();
s.pop();
for(int i=adiacenta[curr].size()-1; i>=0; i--){
int nod = adiacenta[curr][i];
if(vis[nod] == 0){
vis[nod] = 1;
s.push(nod);
}
}
}
}
}
return res;
}
};
ifstream in("dfs.in");
ofstream out("dfs.out");
int main(){
int n, m;
in>>n>>m;
vector<vector<int>> mat(n);
for(int i=0; i<m; i++){
int aux1, aux2;
in>>aux1>>aux2;
mat[aux1-1].push_back(aux2-1);
}
graf x(mat, n, m);
out<<x.dfs();
return 0;
}