Cod sursa(job #592261)

Utilizator APOCALYPTODragos APOCALYPTO Data 27 mai 2011 14:35:08
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.43 kb
using namespace std;
#include<iostream>
#include<fstream>
#include<vector>
#include<stack>
#define nmax 100010
#define pb push_back
ofstream fout("ctc.out");
vector<vector<int> > sol;
vector<int> G[nmax],GT[nmax];
stack<int> s;
int N,M;
 vector<int> comp;
 int viz1[nmax],viz2[nmax];
void dfs1(int x)
{
    if(viz1[x]) return;
    viz1[x]=1;
    vector<int>::iterator it;
    for(it=G[x].begin();it<G[x].end();it++)
    {
        dfs1(*it);
    }
    s.push(x);
}

void dfs2(int x)
{
    if(viz2[x]) return;
    viz2[x]=1;
    comp.pb(x);
    vector<int>::iterator it;
    for(it=GT[x].begin();it<GT[x].end();it++)
    {
        dfs2(*it);
    }
}

void solve()
{
    int i;
   for(i=1;i<=N;i++)
   {
       if(!viz1[i])
       {
           dfs1(i);
       }
   }

   int u;
   while(!s.empty())
   {
       u=s.top();
       s.pop();
       if(!viz2[u])
       {
           comp.clear();
           dfs2(u);
           sol.pb(comp);

       }
   }
   fout<<sol.size()<<"\n";
   vector<vector<int> >::iterator it;
   vector<int>::iterator jt;
   for(it=sol.begin();it<sol.end();++it)
   {
       for(jt=it->begin();jt<it->end();++jt)
       {
           fout<<*jt<<" ";
       }
       fout<<"\n";
   }
}

void cit()
{
    ifstream fin("ctc.in");
    fin>>N>>M;
    int i,x,y;
    for(i=1;i<=M;i++)
    {
        fin>>x>>y;
        G[x].pb(y);
        GT[y].pb(x);

    }
    fin.close();
}

int main()
{
    cit();

    solve();

    fout.close();

    return 0;
}