Cod sursa(job #431818)

Utilizator liviu12345Stoica Liviu liviu12345 Data 1 aprilie 2010 14:11:08
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.44 kb
#include<fstream>
using namespace std;
struct timpi 
{
  int intrare;
  int iesire;
};
int sel[1000],n,m,listadirect[1000][1000],listainvers[1000][1000],k,iesiri[1000];
timpi A[1000];
ofstream g ("ctc.out");
void DF (int i)
{
  int j;
  sel[i]=1;
  A[i].intrare=k++;
  for (j=1;j<=listadirect[i][0];j++)
  {
    if (sel[listadirect[i][j]]==0)
    {
      DF(listadirect[i][j]);
      k++;
    }
  }
  A[i].iesire=k;
  iesiri[++m]=i;
}
void DF2(int i)
{
  int j;
  sel[i]=0;
  for (j=1;j<=listainvers[i][0];j++)
  {
    if(sel[listainvers[i][j]]==1)
    {
      if (A[i].iesire>A[listainvers[i][j]].intrare)
      {
	DF2(listainvers[i][j]);
      }
    }
  }
  g<<i<<" ";
}
void DF3(int i)
{
  int j;
  sel[i]=0;
  for (j=1;j<=listainvers[i][0];j++)
  {
    if(sel[listainvers[i][j]]==1)
    {
      if (A[i].iesire>A[listainvers[i][j]].intrare)
      {
	DF3(listainvers[i][j]);
      }
    }
  }

}
int main ()
{
  int i, j,h=0;
  ifstream f ("ctc.in");

  f>>n;
  while (f>>i>>j)
  {
    listadirect[i][++listadirect[i][0]]=j;
    listainvers[j][++listainvers[j][0]]=i;
  }
  for (i=1;i<=n;i++)
  {
    if (sel[i]==0)
    {
      DF(i);
      k++;
    }
  }
  
  for(i=m;i>=1;i--)
  {
    if (sel[iesiri[i]]==1)
    {
     
      DF3(iesiri[i]);
      h++;
    }
  }
  g<<h<<endl;
 
  for (i=1;i<=n;i++)
    sel[i]=1;
  
  for(i=m;i>=1;i--)
  {
    if (sel[iesiri[i]]==1)
    {
     
      DF2(iesiri[i]);
      g<<endl;
    }
  }
  
  f.close();
  g.close();
  return 0;
}