Cod sursa(job #2720744)

Utilizator Fatu_SamuelFatu Samuel Fatu_Samuel Data 11 martie 2021 11:22:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#include <stack>
#include <bitset>
#include <iostream>

using namespace std;

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

const int nMax = 100000 + 10;

int n, m;

vector < int > l[nMax];
vector < int > lT[nMax];

stack < int > stk;

bitset < nMax > viz;

vector < int > nodes[nMax];

void Dfs(int nod)
{
    viz[nod] = 1;

    for (int next : l[nod])
    {
        if (!viz[next])
        {
            Dfs(next);
        }
    }


    stk.push(nod);
}

void DfsT(int nod, int value)
{
    nodes[value].push_back(nod);

    viz[nod] = 0;

    for (int next : lT[nod])
    {
        if (viz[next])
        {
            DfsT(next, value);
        }
    }
}

int main()
{
    fin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        int a, b;

        fin >> a >> b;

        l[a].push_back(b);
        lT[b].push_back(a);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!viz[i])
        {
            Dfs(i);
        }
    }

    int comps = 0;

    while (!stk.empty())
    {
        if (viz[stk.top()])
        {
            DfsT(stk.top(), ++comps);
        }

        stk.pop();
    }
    
    fout << comps << '\n';

    for (int i = 1; i <= comps; i++)
    {
        for (int e : nodes[i])
        {
            fout << e << ' ';
        }
        fout << '\n';
    }

    fin.close();
    fout.close();
    return 0;
}