Pagini recente » Cod sursa (job #2679461) | Cod sursa (job #2484745) | Cod sursa (job #2982528) | Cod sursa (job #2917554) | Cod sursa (job #535729)
Cod sursa(job #535729)
#include<fstream>
#include<vector>
#define maxn 100005
using namespace std;
class graph {
int n;
vector <int> v[maxn];
int comp;
int viz[maxn];
public:
graph(int n) {
this -> n = n;
comp = 0;
}
void add_edge(int x, int y) {
v[x].push_back(y);
}
int getcomp() {
return comp;
}
void components() {
for (int i = 1; i <= n; i++)
viz[i] = 0;
for (int i = 1; i <= n; i++) {
if (viz[i] == 0) {
comp++;
dfs(i);
}
}
}
void dfs(int nod) {
viz[nod] = 1;
for (int i = 0; i < v[nod].size(); i++) {
if (viz[v[nod][i]] == 0) {
viz[v[nod][i]] = 1;
dfs(v[nod][i]);
}
}
}
};
int main() {
ifstream f("dfs.in");
ofstream g("dfs.out");
int n, m, s, x, y;
f >> n >> m;
graph gr = graph(n);
for (int i = 1; i <= m; i++) {
f >> x >> y;
gr.add_edge(x, y);
}
gr.components();
g << gr.getcomp() << '\n';
return 0;
}