Pagini recente » Cod sursa (job #2795427) | Cod sursa (job #1744672) | Cod sursa (job #986889) | Cod sursa (job #2665139) | Cod sursa (job #2620571)
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
vector<int> lista[100010];
int freq[100010];
void dfs(int start) {
stack<int> s;
s.push(start);
while (!s.empty()) {
int top = s.top();
s.pop();
if (!freq[top]) {
freq[top] = 1;
for (int i = 0; i < lista[top].size(); i++)
s.push(lista[top][i]);
}
}
}
int main() {
int n, m;
int x, y;
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
lista[x].push_back(y);
lista[y].push_back(x);
}
int counter = 0;
for (int i = 1; i <= n; i++) {
if (!freq[i]) {
dfs(i);
counter++;
}
}
/*for (int i = 1; i <= n; i++) {
cout << "#" << i << ": ";
for (int j = 0; j < lista[i].size(); j++)
cout << lista[i][j] << " ";
cout << "\n";
}*/
fout << counter;
return 0;
}