Pagini recente » Cod sursa (job #3316871) | Cod sursa (job #660272) | Cod sursa (job #784972) | Cod sursa (job #785076) | Cod sursa (job #3316883)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int n, m, nr;
vector<int> L[10000001];
int viz[10000001];
void DFS(int nod) {
viz[nod] = 1;
for (auto vecin : L[nod]) {
if (viz[vecin] == 0)
DFS(vecin);
}
}
int main() {
ifstream fin("dfs.in");
fin >> n >> m;
for (int i = 1 ; i <= n ; i++) {
int nod;
fin >> nod;
L[i].push_back(nod);
}
for (int i = 1 ; i <= n ; i++) {
if (viz[i] == 0){
nr++;
DFS(i);
}
}
ofstream fout("dfs.out");
fout << nr;
}
// #include <bits/stdc++.h>
// using namespace std;
//
// int main() {
// ios::sync_with_stdio(false);
// cin.tie(nullptr);
//
// int N, M;
// if (!(cin >> N >> M)) return 0;
//
// vector<vector<int>> adj(N + 1);
// for (int i = 0; i < M; ++i) {
// int x, y;
// cin >> x >> y;
// adj[x].push_back(y);
// adj[y].push_back(x);
// }
//
// vector<char> visited(N + 1, 0);
// int components = 0;
//
// for (int i = 1; i <= N; ++i) {
// if (visited[i]) continue;
// ++components;
// // iterative DFS using stack
// stack<int> st;
// st.push(i);
// while (!st.empty()) {
// int u = st.top(); st.pop();
// if (visited[u]) continue;
// visited[u] = 1;
// for (int v : adj[u])
// if (!visited[v]) st.push(v);
// }
// }
//
// cout << components << '\n';
// return 0;
// }