Cod sursa(job #1167437)

Utilizator radu2004GOLD radu radu2004 Data 4 aprilie 2014 23:54:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.42 kb
#include <stdio.h>
#include <vector>
#include <algorithm>
#include <math.h>


using namespace std;
int i,nr,use[100002],rad[100002],n,m,y,nr1;
vector <int> v[100002],s,a[100002];
FILE *f,*g;
void compune (int i)
{   int x;
    int j;
    use[i]=nr;
    rad[i]=nr;
    nr++;
    s.push_back (i);
    for (j=0;j<v[i].size();j++)
      {
          x=v[i].at(j);
          if (!use[x]) {
                       compune (x);
                       rad[i]=min (rad[i],rad[x]);
                        }
              else   if (use[x]>0) rad[i]=min (rad[i],rad[x]);
      }
      if (rad[i]==use[i])
      {
          while (s.back ()!=i)   {

                                     a[nr1].push_back(s.back ());
                                     use[s.back()]=-1;
                                     s.pop_back ();
                                 }
          a[nr1++].push_back(s.back ());
           use[s.back()]=-1;
          s.pop_back ();
      }
}

int main()
{   f=fopen ("ctc.in","r");
    g=fopen ("ctc.out","w");
    int x;
    fscanf (f,"%d%d",&n,&m);
    for (i=1;i<=m;i++)
    {
     fscanf (f,"%d%d",&x,&y);
     v[x].push_back(y);
    }
    for (i=1;i<=n;i++)
      if (use[i]==0) compune (i);
   fprintf (g,"%d\n",nr1);
   for (i=0;i<nr1;i++)
   {
    while (!a[i].empty())
          {fprintf (g,"%d ",a[i].back());a[i].pop_back ();}
     fprintf (g,"\n");
   }
    return 0;
}