Pagini recente » Cod sursa (job #293573) | Cod sursa (job #3161058) | Cod sursa (job #2494666) | Cod sursa (job #1717757) | Cod sursa (job #2432059)
#include <fstream>
#include <iostream>
#include <vector>
#define nmax 100001
using namespace std;
ifstream f("dfs.in");
ofstream g("dfs.out");
class graph{
private:
vector<int> edges[nmax];
vector<bool> visited;
int nodes=0;
int numcomponents=0;
public:
graph(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){
numcomponents++;
dfs(i);
}
}
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();
}