Cod sursa(job #2217271)

Utilizator HumikoPostu Alexandru Humiko Data 29 iunie 2018 20:14:03
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.33 kb
#include <bits/stdc++.h>
#define lim 100005

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

vector <int> graph[lim];
vector <int> reversed_Graph[lim];
vector <int> answer[lim];
stack <int> road;
int f[lim];

void resetFrequency(int n)
{
    for ( int i = 1; i <= n; ++i )
        f[i] = 0;
}

void dfs( int node )
{
    f[node] = 1;
    for ( auto x:graph[node] )
        if ( f[x] == 0 )
            dfs(x);
    road.push(node);
}

void reverseDfs( int node, int solution_Count )
{
    f[node] = 1;
    for ( auto x:reversed_Graph[node] )
        if ( f[x] == 0 )
            reverseDfs(x, solution_Count);
    answer[solution_Count].push_back(node);
}

int main()
{
    int n, m;
    fin>>n>>m;
    int a, b;
    while ( m-- )
    {
        fin>>a>>b;
        graph[a].push_back(b);
        reversed_Graph[b].push_back(a);
    }
    for ( int i = 1; i <= n; ++i )
        if ( f[i] == 0 )
            dfs(i);
    resetFrequency(n);
    int solution_Count = 0;
    while ( !road.empty() )
    {
        if ( f[road.top()] == 0 )
            reverseDfs(road.top(), ++solution_Count);
        road.pop();
    }
    fout<<solution_Count<<'\n';
    for ( int i = 1; i <= n; ++i )
    {
        for ( auto x:answer[i] )
            fout<<x<<" ";
        fout<<'\n';
    }
}