Cod sursa(job #1374265)

Utilizator jordasIordache Andrei Alexandru jordas Data 5 martie 2015 01:35:49
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 3.17 kb
#include <fstream>
#define nMax 101

using namespace std;

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

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

 struct struct2
 {
     int v;
     int ft;
 };

 bool visited[nMax];
 int n,time,k;
 int scc[nMax];
 struct2 t[nMax];
 node *head[nMax],*rhead[nMax];
 node *tail[nMax],*rtail[nMax];

 void add_graph(int A, int B)
 {
     if(!head[A])
     {
         head[A]=new node();

         head[A]->data=B;
         head[A]->next=NULL;
         tail[A]=head[A];
     }
     else
     {
         node *temp;

         temp=new node();

         temp->data=B;
         temp->next=NULL;
         tail[A]->next=temp;
         tail[A]=temp;
     }
 }

 void add_rgraph(int A, int B)
 {
     if(!rhead[A])
     {
         rhead[A]=new node();

         rhead[A]->data=B;
         rhead[A]->next=NULL;
         rtail[A]=rhead[A];
     }
     else
     {
         node *temp;

         temp=new node();

         temp->data=B;
         temp->next=NULL;
         rtail[A]->next=temp;
         rtail[A]=temp;
     }
 }

 void dfs_graph(int i)
 {
     node *temp;

     temp=head[i];

     visited[i]=true;

     while(temp)
     {
         if(!visited[temp->data])
            dfs_graph(temp->data);

         temp=temp->next;
     }

     t[i].ft=++time;
 }

 void dfs_rgraph(int i)
 {
     node *temp;

     temp=rhead[i];

     scc[i]=k;
     visited[i]=true;

     while(temp)
     {
         if(!visited[temp->data])
            dfs_rgraph(temp->data);

         temp=temp->next;
     }
 }

 void sort()
 {
     int i,j;
     struct2 aux;

     for(i=1;i<n;i++)
        for(j=i+1;j<=n;j++)
           if(t[i].ft<t[j].ft)
           {
               aux=t[i];
               t[i]=t[j];
               t[j]=aux;
           }
 }

 void show(int j)
 {
     int i;
     node *temp;

     for(i=1;i<=n;i++)
     {
         y<<i<<" --> ";

         if(j==0)
            temp=head[i];
         else
            temp=rhead[i];

         while(temp)
         {
             y<<temp->data<<' ';

             temp=temp->next;
         }

         y<<'\n';
     }
     y<<'\n';
 }

int main()
{
    int i;
    int m;

    x>>n>>m;

    int A,B;

    while(x>>A && x>>B)
    {
        add_graph(A,B);
        add_rgraph(B,A);
    }

    //show(0);
    //show(1);

    for(i=1;i<=n;i++)
       t[i].v=i;

    for(i=1;i<=n;i++)
       if(!t[i].ft)
       {
           dfs_graph(i);
       }

    sort();
/*
    for(i=1;i<=n;i++)
       y<<i<<' ';
    y<<'\n';
*/
/*
    for(i=1;i<=n;i++)
       y<<t[i].v<<' ';
    y<<'\n';
    for(i=1;i<=n;i++)
       y<<t[i].ft<<' ';
    y<<'\n';
    y<<'\n';
*/

    for(i=1;i<=n;i++)
       visited[i]=false;

    for(i=1;i<=n;i++)
       if(!visited[t[i].v])
       {
           k++;
           dfs_rgraph(t[i].v);
       }
    y<<k<<'\n';

    for(i=1;i<=k;i++)
    {
        for(int j=1;j<=n;j++)
           if(scc[j]==i)
              y<<j<<' ';
        y<<'\n';
    }
/*
    for(i=1;i<=n;i++)
       y<<scc[i]<<' ';
    y<<'\n';
*/
    return 0;
}