Cod sursa(job #526893)

Utilizator icepowdahTudor Didilescu icepowdah Data 29 ianuarie 2011 18:49:22
Problema Parcurgere DFS - componente conexe Scor 15
Compilator cpp Status done
Runda Arhiva educationala Marime 1.22 kb
#include <fstream>
#include <queue>
using namespace std;

#define NMAX 100000

struct neighbor {
  int id;
  neighbor* next;
};

int N, M;
bool visited[NMAX];
neighbor* adj_list[NMAX];
ofstream g("dfs.out");

void readInput();
void BFS(int s);

int main(void)
{
  readInput();
  
  int comp_conexe = 0;
  for (int i=0;i<N;i++)
  {
    if (!visited[i])
    {
      comp_conexe++;     
      BFS(i);      
    }
  }
  
  g << comp_conexe << "\n";

  g.close();
  return 0;
}

void readInput()
{
  int from, to;
  ifstream f("dfs.in");

  f >> N >> M;
  for (int i=0;i<M;i++)
  {
    f >> from >> to;
    neighbor* x = new neighbor;
    x->id = to-1;
    x->next = adj_list[from-1];
    adj_list[from-1] = x;

    x = new neighbor;
    x->id = from-1;
    x->next = adj_list[to-1];
    adj_list[to] = x;
  }

  f.close();
}

void BFS(int s)
{
  queue<int> Q;

  visited[s] = true;  
  Q.push(s);
  while (!Q.empty())
  {
    int x = Q.front();
    Q.pop();
       
    neighbor* it = adj_list[x];
    while (it != NULL)
    {
      if (!visited[it->id])
      {        
        visited[it->id] = true;
        Q.push(it->id);
      }
      it = it->next;
    }
  }
}