Mai intai trebuie sa te autentifici.
Cod sursa(job #2454740)
Utilizator | Data | 9 septembrie 2019 20:02:25 | |
---|---|---|---|
Problema | Parcurgere DFS - componente conexe | Scor | 80 |
Compilator | cpp-64 | Status | done |
Runda | Arhiva educationala | Marime | 0.82 kb |
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
#define ARRAY_MAX 100000
int N, M, X, Y, Connected, Next;
vector <int> Edge[ARRAY_MAX];
bool Visited[ARRAY_MAX];
void DFS(int Node) {
Visited[Node] = 1;
for (unsigned i = 0; i < Edge[Node].size(); i++) {
Next = Edge[Node][i];
if (!Visited[Next])
DFS(Next);
}
}
void Read() {
fin >> N >> M;
for (int i = 1; i <= M; i++) {
fin >> X >> Y;
Edge[X].push_back(Y);
Edge[Y].push_back(X);
}
}
void Write() {
for (int i = 1; i <= N; i++)
if (!Visited[i]) {
Connected++;
DFS(i);
}
fout << Connected;
}
int main() {
Read();
Write();
}