Pagini recente » Cod sursa (job #1840459) | Cod sursa (job #1725526) | Cod sursa (job #1301420) | Cod sursa (job #1946865) | Cod sursa (job #2229980)
#include <bits/stdc++.h>
#define MaximumEdges 200000
#define MaximumNodes 100000
std::ifstream InFile("dfs.in");
std::ofstream OutFile("dfs.out");
int N, M;
// Assuming the data file won't have duplicate entries we can use a list
std::list <int> Adj[MaximumNodes];
bool Seen[MaximumNodes];
// The answer
int CompCount;
void DFS(int StartingIndex) {
Seen[StartingIndex] = 1;
for (auto Index : Adj[StartingIndex])
if(!Seen[Index])
DFS(Index);
}
void Citire() {
InFile >> N >> M;
for (int i=0, x, y; i<M; i++) {
InFile >> x >> y;
// Because I can
x--, y--;
Adj[x].push_front(y);
Adj[y].push_front(x);
}
InFile.close();
}
void Rezolvare() {
for (int i=0; i<N; i++)
if(!Seen[i]) {
DFS(i);
CompCount ++;
}
OutFile << CompCount;
}
int main()
{
Citire();
Rezolvare();
InFile.close();
OutFile.close();
return 0;
}