Cod sursa(job #2314916)

Utilizator davidbejenariu2David Bejenariu davidbejenariu2 Data 9 ianuarie 2019 11:34:12
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>
#define N 100005

using namespace std;

ifstream fin( "ctc.in" );
ofstream fout( "ctc.out" );

vector <int> G[N], Gt[N];
int n, m, ct;
stack <int> S;
bool viz[N], vizt[N];
vector <int> comp[N];

void read()
{
    int i, x, y;
    fin >> n >> m;
    for ( i = 1; i <= m; ++i )
         { fin >> x >> y;
           G[x].push_back(y);
           Gt[y].push_back(x);
         }
    fin.close();
}

void topo( int x )
{
    viz[x] = 1;
    int i;
    for ( i = 0; i < G[x].size(); ++i )
         if ( !viz[G[x][i]] )
             topo(G[x][i]);
    S.push(x);
}

void DFS( int x )
{
    comp[ct].push_back(x);
    int i;
    vizt[x] = 1;
    for ( i = 0; i < Gt[x].size(); ++i )
         if ( !vizt[Gt[x][i]] )
             DFS(Gt[x][i]);
}

void solve()
{
    int i, j, x;
    for ( i = 1; i <= n; ++i )
         if ( !viz[i] )
             topo(i);
    while ( !S.empty() )
           { x = S.top();
             S.pop();
             if ( !vizt[x] )
                 { ct++;
                   DFS(x);
                 }
           }
    fout << ct << '\n';
    for ( i = 1; i <= ct; ++i )
         { sort( comp[i].begin(), comp[i].end() );
           for ( j = 0; j < comp[i].size(); ++j )
                fout << comp[i][j] << ' ';
           fout << '\n';
         }
}

int main()
{   read();
    solve();
    return 0;
}