Cod sursa(job #1303011)

Utilizator jordasIordache Andrei Alexandru jordas Data 27 decembrie 2014 15:33:33
Problema Parcurgere DFS - componente conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.55 kb
#include <fstream>

using namespace std;

 ifstream x ("dfs.in");
 ofstream y ("dfs.out");

 struct node
 {
     int i;
     node *next;
 };

 int n,m;
 int a[100001];
 node *temp;
 node *current;
 node *head[100001];

 void add(int X, int Y)
 {
     if(head[X]==NULL)
     {
         head[X]=new node();

         head[X]->i=Y;
         head[X]->next=NULL;
     }
     else
     {
         current=new node();

         current=head[X];
         while(current->next)
            current=current->next;

         temp=new node();

         temp->i=Y;
         temp->next=NULL;
         current->next=temp;
     }
 }

 void dfs(int i, int k)
 {
     a[i]=k;

     if(head[i])
     {
         node *current;

         current=head[i];

         while(current)
         {
             if(a[current->i]==0)
                dfs(current->i,k);

             current=current->next;
         }
     }
 }

int main()
{
    int i;

    x>>n>>m;

    int X,Y;

    for(i=1;i<=m;i++)
    {
        x>>X>>Y;
        add(X,Y);
        add(Y,X);
    }
/*
    for(i=1;i<=n;i++)
    {
        y<<i<<" --> ";

        current=head[i];

        while(current)
        {
            y<<current->i<<' ';
            current=current->next;
        }

        y<<'\n';
    }
    y<<'\n';
*/
    int k=0;

    for(i=1;i<=n;i++)
       if(a[i]==0)
       {
           k++;
           dfs(i,k);
       }

    y<<k<<'\n';
/*
    for(i=1;i<=n;i++)
       y<<a[i]<<' ';
    y<<'\n';
*/
    return 0;
}