Cod sursa(job #526897)

Utilizator icepowdahTudor Didilescu icepowdah Data 29 ianuarie 2011 18:54:13
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.09 kb
#include <fstream>
using namespace std;

#define NMAX 100000

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

int N, M;
bool visited[NMAX];
neighbor* adj_list[NMAX];

void readInput();
void add_edge(int from, int to);
void dfs_visit(int s);

int main(void)
{
  ofstream g("dfs.out");

  readInput();
  
  int comp_conexe = 0;
  for (int i=0;i<N;i++)
  {
    if (!visited[i])
    {
      comp_conexe++;
      dfs_visit(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-1] = x;
  }

  f.close();
}

void dfs_visit(int s)
{
  visited[s] = true;
  neighbor* it = adj_list[s];
  while (it != NULL)
  {
    if (!visited[it->id])
    {
      dfs_visit(it->id);
    }
    it = it->next;
  }
}