Cod sursa(job #662981)

Utilizator EstarDaian Dragos Estar Data 17 ianuarie 2012 16:59:19
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.1 kb
#include <fstream>
#include <vector>

using namespace std;

ifstream fi("dfs.in");
ofstream fo("dfs.out");

struct dfsearch{
  vector<int> next;
  bool done;
  dfsearch(){
    done=0;
  }
};

int main(){
  int n , m;
  vector<dfsearch> graf;
  vector<int> coada;
  fi>>n>>m;
  for(int i=0;i<n;i++)
  graf.push_back(dfsearch());
  for(int i=0;i<m;i++){
    int x , y;
    fi>>x>>y;
    graf[x-1].next.push_back(y-1);
    graf[y-1].next.push_back(x-1);
  }
  int k=0;
  for(int i=0;i<n;i++){
    if(!graf[i].next.size()&&!graf[i].done){graf[i].done=1;k++;continue;}
    if(graf[i].done){continue;}
    if(!graf[i].done){k++;graf[i].done=1;}
    for(int j=0;j<(signed)graf[i].next.size();j++){
      coada.push_back(graf[i].next[j]);
    }
    int j=0;
    while(j!=(signed)coada.size()){
        graf[coada[j]].done=1;
      for(int l=0;l<(signed)graf[coada[j]].next.size();l++){
        if(!graf[graf[coada[j]].next[l]].done)
        coada.push_back(graf[coada[j]].next[l]);
        graf[graf[coada[j]].next[l]].done=1;
      }
      j++;
    }
    coada.clear();
  }
  fo<<k;
}