Cod sursa(job #476936)

Utilizator APOCALYPTODragos APOCALYPTO Data 12 august 2010 19:48:19
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#define Nmax 100005
#define pb push_back
#define foreach(v)  for(typeof (v).begin() it=(v).begin();it!=(v).end();it++)
vector<int> G[Nmax];
vector<int> TG[Nmax];
vector<int> ans[Nmax];
vector<int>::iterator it;
ofstream fout("ctc.out");
int N,M,nr=0,postord[Nmax],viz[Nmax];

void DFS(int u)
{    viz[u]=1;
vector<int>::iterator it;
    for(it=G[u].begin();it!=G[u].end();it++)
       if(viz[*it]==0)
        {    //cout<<*it<<" ";
            DFS(*it);

        }

   postord[++nr]=u;


}
void DFS2(int u)
{vector<int>::iterator it;
    viz[u]=0;
    for(it=TG[u].begin();it!=TG[u].end();it++)
       if(viz[*it])
        DFS2(*it);
    ans[nr].pb(u);

}
void solve()
{
    int i,j;
    for(i=1;i<=N;i++)
     if(!viz[i])
      {DFS(i);

      }
      nr=0;


    for(i=N;i>=1;i--)
     if(viz[postord[i]])
      {nr++;
      DFS2(postord[i]);
      }
    fout<<nr<<"\n";
    for(i=1;i<=nr;i++)
    {
     for(j=0;j<ans[i].size();j++)
       fout<<ans[i][j]<<" ";
     fout<<"\n";
    }
}
void cit()
{int i,x,y;
    ifstream fin("ctc.in");
    fin>>N>>M;
    for(i=1;i<=M;i++)
    {  fin>>x>>y;
       G[x].pb(y);
       TG[y].pb(x);
    }
    fin.close();



}
int main()
{

    cit();
    solve();
    fout.close();
    return 0;
}