Cod sursa(job #674480)

Utilizator hiticas_abelhiticasabel hiticas_abel Data 6 februarie 2012 12:47:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.16 kb
#include<fstream>
#include<vector>
#include<bitset>
#include<algorithm>
 
 #define maxn 100100
using namespace std;

vector <int> G[maxn],Gt[maxn],s[maxn],A;
int n,m,t[maxn],sol,nr;
bitset <maxn>viz;

  void df(int x)
  {int i;
   viz[x]=1;
   for(i=0;i<(int) G[x].size();++i)
   if(!viz[G[x][i]])
   df(G[x][i]);
   
   t[x]=++nr;     
  
  }
  void df2(int x)
  {
       int i;
  s[sol].push_back(x);
  viz[x]=1;
  for(i=0;i<(int) Gt[x].size();++i)
  if(!viz[Gt[x][i]])
  df2(Gt[x][i]);

}
inline bool cmp(int a, int b)
{
return t[a]>t[b];
}

int main()
{
int i,j,a,b;
ifstream f("ctc.in");
ofstream g("ctc.out");

f>>n>>m;
  for(i=1;i<=m;++i)
  {
   f>>a>>b;
 G[a].push_back(b);
   Gt[b].push_back(a);                 
  }
  for(i=1;i<=n;++i)
  if(!viz[i])
  df(i);
  for(i=1;i<=n;++i)
  A.push_back(i);
  sort(A.begin(),A.end(),cmp);
  
  viz.reset();
  
  for(i=0;i<n;++i)
  if(!viz[A[i]])
  {
  sol++;
  df2(A[i]);              
  }
  g<<sol<<"\n";
  
  for(i=1;i<=sol;++i)
    { for(j=0;j<(int)s[i].size();++j)
     g<<s[i][j]<<" ";
   g<<"\n";
   }
     f.close();
     g.close();
     return 0;
  }