Cod sursa(job #2024852)

Utilizator OldpugAlex Ionescu Oldpug Data 21 septembrie 2017 12:37:02
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.78 kb
#include <stdio.h>

constexpr int null = 0;

struct Node
{
  int Idx;
  Node *Next;
};

void Tie(Node *&dest, int idx)
{
  auto p = new Node;

  p->Idx = idx;
  p->Next = dest;

  dest = p;
}

Node **node;
bool *seen;

void Search(int idx)
{
  seen[idx] = true;

  for (auto p = node[idx]; p != null; p = p->Next)
    if (!seen[p->Idx])
      Search(p->Idx);
}

int main()
{
  freopen("dfs.in", "r", stdin);
  freopen("dfs.out", "w", stdout);

  int n, m;
  scanf("%d %d", &n, &m);

  node = new Node *[n];
  seen = new bool[n];

  for (auto i = 0; i < m; ++i)
  {
    int x, y;
    scanf("%d %d", &x, &y);

    Tie(node[--x], --y);
    Tie(node[y], x);
  }

  auto count = 0;
  for (auto i = 0; i < n; ++i)
    if (!seen[i])
    {
      ++count;
      Search(i);
    }

  printf("%d\n",count);
}