Cod sursa(job #2147742)

Utilizator VarticeanNicolae Varticean Varticean Data 28 februarie 2018 22:49:02
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>
#define nmax 100005
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector < int > v[nmax],vv[nmax];
bitset < nmax > viz;
vector < int > sol[nmax];
stack < int > s;
int n,m,k;
void read()
{
   in >>  n >> m;
   int a,b;
   for(int i=1; i<=m; i++)
   {
        in >> a >> b;
        v[a].push_back(b);
        vv[b].push_back(a);
   }
}
void topsort( int nod )
{
     viz[nod] = 1;
     for(int i=0; i<v[nod].size(); i++)
          if( !viz[v[nod][i]] ) topsort( v[nod][i]);
     s.push(nod);
}
void dfs( int nod )
{
     viz[nod] = 1;
     sol[k].push_back(nod);
     for(int i=0; i<vv[nod].size(); i++)
          if( !viz[vv[nod][i]] ) dfs( vv[nod][i] );
}
int main()
{
     read();
     for(int i=1; i<=n; i++)
          if( !viz[i] ) topsort(i);
     viz.reset();

     while( !s.empty() )
     {
          int head = s.top();
          s.pop();
          if( !viz[head] ) k++, dfs(head);
     }
    out << k << '\n';
   for(int i=1; i<=k; i++)
   {
        for(int j=0; j<sol[i].size(); j++)
          out << sol[i][j] << ' ';
          out << '\n';
   }
    return 0;
}