Pagini recente » Rating Enache Tudor (tudorenache) | Cod sursa (job #2109447) | Cod sursa (job #243337) | Cod sursa (job #760599) | Cod sursa (job #3122484)
#include <bits/stdc++.h>
using namespace std;
static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005
// n = numar de noduri, m = numar de muchii/arce
int n, m;
// adj[node] = lista de adiacenta a nodului node
// exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
vector<int> adj[NMAX];
void read_input() {
ifstream fin("dfs.in");
fin >> n >> m;
for (int i = 1, x, y; i <= m; i++) {
fin >> x >> y; // arc (x, y)
adj[x].push_back(y);
}
fin.close();
}
void DFS(int src, vector<int> &visited) {
for (int i = 0; i < adj[src].size(); i++) {
if (visited[adj[src][i]] == 0) {
visited[adj[src][i]] = 1;
DFS(adj[src][i], visited);
}
}
}
int main() {
ofstream fout("dfs.out");
read_input();
vector<int> visited(n + 1, 0);
int count = 0;
for (int i = 1; i <= n; i++) {
if (visited[i] == 0) {
visited[i] = 1;
DFS(i, visited);
count++;
}
}
fout << count;
fout.close();
return 0;
}