Pagini recente » Cod sursa (job #3367547) | Cod sursa (job #3367659) | Cod sursa (job #3367517) | Cod sursa (job #3367658) | Cod sursa (job #3367521)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("dfs.in");
ofstream fout ("dfs.out");
int n, m;
/**
Matrice de adiacenta
6 3
1 2
1 4
3 5
1 2 3 4 5
1 0 1 0 1 0
2 1 0 0 0 0
3 0 0 0 0 1
4 1 0 0 0 0
5 0 0 1 0 0
Liste de adiacenta
1: 2 4
2: 1
3: 5
4: 1
5: 3
*/
vector < vector <int > > adj;
vector <int> viz;
void DFS(int nod) {
viz[nod] = 1;
for (int i : adj[nod])
if (viz[i] == 0)
DFS(i);
}
int main()
{
int cnt = 0; /// numarul de componente conexe
fin >> n >> m;
adj.resize(n + 5);
viz.resize(n + 5);
for (int i = 1; i <= m; i++) {
int x, y;
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
for (int i = 1; i <= n; i++)
if (viz[i] == 0) {
DFS(i);
cnt++;
}
fout << cnt << "\n";
return 0;
}