Nu aveti permisiuni pentru a descarca fisierul grader_test5.in
Cod sursa(job #2229964)
Utilizator | Data | 8 august 2018 16:34:15 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 100 |
Compilator | cpp | Status | done |
Runda | Arhiva educationala | Marime | 0.64 kb |
#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;
}