Cod sursa(job #2147745)

Utilizator VarticeanNicolae Varticean Varticean Data 28 februarie 2018 22:51:43
Problema Componente tare conexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <bits/stdc++.h>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
vector < int > v[100005], vv[100005], sol[100005];
stack < int > s;
bool viz[100005];
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 head)
{
     viz[head] = 1;
     for(int i=0; i<v[head].size(); i++)
          if( !viz[ v[head][i] ] ) topsort( v[head][i] );
     s.push(head);
}
void dfs( int head )
{
     viz[head] = 0;
     sol[k].push_back(head);
     for(int i=0; i<vv[head].size(); i++)
          if( viz[ vv[head][i]] ) dfs( vv[head][i]);
}
int main()
{
     read();
     for(int i=1; i<=n; i++)
          if( !viz[i]) topsort(i);
     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;
}