Pagini recente » Cod sursa (job #2938799) | Cod sursa (job #3256559) | Cod sursa (job #1484929) | Cod sursa (job #851778) | Cod sursa (job #3337204)
// #include <iostream>
// #include <fstream>
// #include <vector>
#include <bits/stdc++.h>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
void dfs(int startNode, vector<vector<int>>& adj, vector<int>& visited) {
visited[startNode] = 1;
// for(int i = ; i < adj[startNode].size(); i++) {
// if(!visited[adj[startNode][i]]) {
// dfs(i, adj, visited);
// }
// }
for(int vecin : adj[startNode]) {
if(!visited[vecin]) {
dfs(vecin, adj, visited);
}
}
}
int cmpConex(vector<vector<int>>& adj) {
int n = adj.size();
int nrConex = 0;
vector<int> visited(n, 0);
for(int i = 1; i < n; i++) {
if(!visited[i]) {
nrConex++;
dfs(i, adj, visited);
}
}
return nrConex;
}
int main() {
int N, M;
fin >> N >> M;
// Initializare liste de adiacenta si vector vizitat
vector<vector<int>> adj(N + 1);
// Citire muchii
for(int i = 0; i < M; i++) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x); // Graf neorientat
}
int conex = cmpConex(adj);
fout << conex;
return 0;
}