Cod sursa(job #805454)

Utilizator ciorile.chioareBogatu Adrian ciorile.chioare Data 31 octombrie 2012 15:07:09
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.53 kb
#include <cstdio>

class ListNode {
  private:
    int data;
  public:
    ListNode *next;
    ListNode(int x) {
      data = x;
    }
    ListNode(int x, ListNode *next) {
      data = x;
      this->next = next;
    }
    int get() {
      return data;
    }
};

class List {
  private:
    ListNode *head;
    bool marked;
  public:
    List() {
      head = NULL;
      marked = false;
    }
    void add(int x) {
      ListNode *new_node = new ListNode(x, head);
      head = new_node;
    }

    ListNode* operator[](int index) {
      ListNode *p = head;
      for(int i = 0; i < index; ++i) {
        if(p == NULL)
          break;
        p = p->next;
      }
      return p;
    }
    void mark() {
      marked = true;
    }
    bool isMarked() {
      return marked;
    }

    ~List() {
      /*
      ListNode *p = head;
      ListNode *q;
      while(p != NULL) {
        q = p;
        p = p->next;
        delete q;
      }
        */
    }
};

List *v;

void dfs(int node) {

  v[node].mark();
  ListNode *p = v[node][0];
  for(; p != NULL; p = p->next) {
    if(!v[p->get()].isMarked())
      dfs(p->get());
  }
}


int main() {

  int n, m;

  FILE* in = fopen("dfs.in", "r");
  FILE* out = fopen("dfs.out", "w");

  fscanf(in, "%d%d", &n, &m);

  int x, y;
  v = new List[n + 1];
  for(int i = 1; i <= m; ++i) {
    fscanf(in, "%d%d", &x, &y);
    v[x].add(y);
    v[y].add(x);
  }

  int compcon = 0;
  for(int i = 1; i <= n; ++i) {
    if(!v[i].isMarked()) {
      compcon++;
      dfs(i);
    }
  }
  fprintf(out, "%d", compcon);
  return 0;
}