Cod sursa(job #1302932)

Utilizator jordasIordache Andrei Alexandru jordas Data 27 decembrie 2014 14:41:21
Problema Parcurgere DFS - componente conexe Scor 5
Compilator cpp Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>

using namespace std;

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

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

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

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

     if(head[i])
     {
         current=head[i];

         while(current)
         {
             dfs(current->i);
             current=current->next;
         }
     }
 }

int main()
{
    int i;

    x>>n>>m;

    int X,Y;

    for(i=1;i<=m;i++)
    {
        x>>X>>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;
        }
    }
/*
    for(i=1;i<=n;i++)
    {
        y<<i<<" --> ";

        current=head[i];

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

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

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