Cod sursa(job #2432056)

Utilizator lucian2015blaugranadevil lucian2015 Data 21 iunie 2019 18:43:19
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.86 kb
#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();

}