Pagini recente » Cod sursa (job #703079) | Cod sursa (job #204529) | Cod sursa (job #1607598) | Rating Bucatea Madalin Stefan (K0nTr0L) | Cod sursa (job #2454743)
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;
ifstream fin("dfs.in");
ofstream fout("dfs.out");
#define ARRAY_MAX 100005
int N, M, X, Y, Connected, Next;
vector <int> Edge[ARRAY_MAX];
bitset <ARRAY_MAX> Visited;
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() {
ios_base::sync_with_stdio(false);
fin.tie(NULL);
Read();
Write();
}