Cod sursa(job #1989631)

Utilizator b10nd3Oana Mancu b10nd3 Data 8 iunie 2017 12:22:07
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 0.63 kb
#include<fstream>
#include<vector>

using namespace std;

#define MAX_NODES 100001

vector <int> graph[MAX_NODES];
int checked[MAX_NODES];

void dfs(int x){
   vector<int>::iterator it;
   checked[x]=1;
   for(it=graph[x].begin(); it!=graph[x].end(); it++){
      if(checked[*it]==0) dfs(*it);   
   }
}


int main(){
ifstream in; ofstream out;
in.open("dfs.in"); out.open("dfs.out");
out.clear();

int i,x,y,n,m,no=0;

in>>n>>m;
for(i=0;i<m;i++){
  in>>x>>y;
  graph[x].push_back(y);
}

for(i=1;i<=n;i++){
  if(checked[i]==0) {
    dfs(i); 
    no++;
  }
}

out<<no;

in.close(); out.close();
return 0;
}