Pagini recente » Cod sursa (job #1495763) | Cod sursa (job #2125004) | Cod sursa (job #56616) | Cod sursa (job #221615) | Cod sursa (job #2259946)
#include <iostream>
#include <fstream>
#include <vector>
#define nmax 100100
using namespace std;
ifstream f("dfs.in");
ofstream gout("dfs.out");
class Graph {
private:
int n;
vector <int> a[nmax];
int* Size;
int* vis;
void dfs(int x) {
vis[x] = 1;
for (int i = 0; i < Size[x]; ++i ) {
int p = a[x][i];
if (vis[p] == 0) {
dfs(p);
}
}
}
public:
Graph(int V) {
this->n = V;
Size = new int [n + 1];
vis = new int [n + 1];
for (int i = 1; i <= n; ++i) {
vis[i] = 0;
Size[i] = 0;
}
}
void addEdge(int n1, int n2) {
a[n1].push_back(n2);
Size[n1] ++;
}
int getConnexComponents() {
int ConnexComponentsNumber = 0;
for (int i = 1; i <= n; ++i) {
if (vis[i] == 0) {
ConnexComponentsNumber ++;
dfs(i);
}
}
return ConnexComponentsNumber;
}
};
int main() {
int n, m;
f >> n >> m;
Graph g(n);
int x, y;
for (int i = 1; i <= m; ++ i) {
f >> x >> y;
g.addEdge(x, y);
g.addEdge(y, x);
}
gout << g.getConnexComponents();
return 0;
}