Pagini recente » Cod sursa (job #1341529) | Cod sursa (job #3178457) | Cod sursa (job #1593127) | Cod sursa (job #2916455) | Cod sursa (job #3160175)
#include <iostream>
#include <cmath>
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
//declarari globale
const int NMAX = 100000;
int vis[NMAX + 1] = {0}; //vector vizitate
vector <int> G[NMAX + 1]; //vector de vectori = lista de adiacenta
void DFS(int x) {
//vizitam nodul
vis[x] = 1;
//cautam vecinii
for(auto next: G[x]) {
//daca inca nu am vizitat vecinul next
if(!vis[next]) {
//marcam ca vizitat
vis[next] = 1;
//continuam parcurgerea
DFS(next);
}
}
}
int main() {
//fisiere I/O
ifstream f("dfs.in");
ofstream g("dfs.out");
//citim graful
int N, M;
f >> N >> M;
for (int i = 1; i <= M ; ++i) {
int a, b;
f >> a >> b;
G[a].push_back(b);
}
//numarul de componente conexe
int nr = 0;
//pentru fiecare varf nevizitat aplicam DFS, fiecare DFS oarcurge o noua componenta conexa
for(int i = 1; i <= N; i++)
if(vis[i] == 0) {
nr++;
DFS(i);
}
//afisam nr componente
g << nr;
f.close();
g.close();
return 0;
}