Cod sursa(job #1879134)

Utilizator remus88Neatu Remus Mihai remus88 Data 14 februarie 2017 18:57:05
Problema Componente tare conexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.19 kb
#include <fstream>
#include <vector>
#include <bitset>
#include <map>
#define Nmax 100009

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

int n,m,x,y,nr, sol[Nmax], nrc;
vector <int> G[Nmax], T[Nmax], ctc[Nmax];
bitset <Nmax> viz;


void ReadInput()
{
    f>>n>>m;
    for (int i=1; i<=m; ++i)
    {
        f>>x>>y;
        G[x].push_back(y);
        T[y].push_back(x);
    }
}

void Dfs(int node)
{
    viz[node]=1;
    for (auto x : G[node])
        if (!viz[x]) Dfs(x);
    ++nr;
    sol[nr] = node;
}

void Dfs_T(int node)
{
    viz[node]=0;
    ctc[nrc].push_back( node );
    for (auto x : T[node])
        if (viz[x]) Dfs_T(x);
}
void Solve()
{
    // sortare topologica
    for (int i=1; i<=n; ++i)
        if (!viz[i]) Dfs(i);

    for (int i = n; i >= 1; --i)
    {
        if (viz[sol[i]])
        {
            ++nrc;
            Dfs_T(sol[i]);
        }

    }
}

void Write()
{
    g<<nrc<<'\n';
    for (int i=1; i<=nrc; ++i)
    {
        for (auto x: ctc[i]) g<<x<<' ';
        g<<'\n';
    }
}

int main()
{
    ReadInput();
    Solve();
    Write();
    f.close();
    g.close();
    return 0;
}