Pagini recente » Istoria paginii utilizator/andy93 | Rezultatele filtrării | Rating Andy Blanaru (andutzu999) | Rezultatele filtrării | Cod sursa (job #2229964)
#include <fstream>
#include <list>
#define NMAX 100001
using namespace std;
int n, m, count;
list<int> graph[NMAX];
int marks[NMAX];
void dfs(int x)
{
// skip if marked
if (marks[x])
return;
marks[x] = 1;
// dfs on neighbors
for (int y : graph[x])
dfs(y);
}
int main()
{
// read input
ifstream fin("dfs.in");
fin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
graph[x].push_back(y);
graph[y].push_back(x);
}
fin.close();
// dfs
for (int i = 1; i <= n; i++) {
if (!marks[i]) {
count++;
dfs(i);
}
}
// print output
ofstream fout("dfs.out");
fout << count;
fout.close();
return 0;
}