Pagini recente » Statistici vacaru flavius (flaviusik) | Cod sursa (job #125612) | Istoria paginii runda/uyr/clasament | Cod sursa (job #2331145) | Cod sursa (job #2432056)
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
class graph{
private:
vector<vector<int> > edges;
vector<bool> visited;
int nodes=0;
int numcomponents=1;
public:
graph(int n){
edges.resize(n,vector<int>(n));
visited.resize(n,0);
nodes=n;
}
void addedge(int x, int y){
edges[x].push_back(y);
}
void dfs(int nod){
int i;
for(i=0;i<edges[nod].size();i++)
if(visited[edges[nod][i]]==0){
visited[edges[nod][i]]=1;
dfs(edges[nod][i]);
}
}
int getnumcomponents(){
int i;
for(i=1;i<nodes;i++){
if(visited[i]==0){
dfs(i);
numcomponents++;
}
}
return numcomponents;
}
};
int main(){
int n, m, x, y, i;
f>>n>>m;
graph graf(n);
for(i=0;i<m;i++){
f>>x>>y;
graf.addedge(x,y);
}
g<<graf.getnumcomponents();
}