Cod sursa(job #1510078)

Utilizator dutzulBodnariuc Dan Alexandru dutzul Data 24 octombrie 2015 15:44:14
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 0.72 kb
#include <iostream>
#include <fstream>

using namespace std;

#define LE 100666
bool viz[LE];

struct Node
{
    int val;
    Node* next;
} *G[LE];

void add(int n1,int n2)
{
    Node *nod=new Node;
    nod->val=n1;
    nod->next=G[n2];
    G[n2]=nod;
}

void dfs(int nod)
{
   Node *X=G[nod];
   viz[nod]=true;

   for(;X!=NULL;X=X->next)
        if (viz[X->val]==false)
             dfs(X->val);
}

ifstream f("dfs.in");
ofstream g("dfs.out");

int main()
{
    int n,m,i,result=0;

    f>>n>>m;


    for(i=1;i<=m;++i)
   {
      int xx,yy;
      f>>xx>>yy;
      add(xx,yy);
      add(yy,xx);
   }

    for(i=1;i<=n;++i)
       if (viz[i]==false)
       {
           dfs(i);
          ++result;
       }

g<<result<<'\n';

  return 0;
}