Cod sursa(job #2024850)

Utilizator OldpugAlex Ionescu Oldpug Data 21 septembrie 2017 12:33:37
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;
}

int n;
Node **node;
bool *seen;

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

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

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

  int 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;
      Dfs(i);
    }

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