Cod sursa(job #2445467)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 4 august 2019 10:44:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.07 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int NMAX = 1e5;

int N, M, q;
int k, rev[NMAX + 5];
bool d[NMAX + 5];
vector <int> g[NMAX + 5];
vector <int> t[NMAX + 5];
vector <int> ctc[NMAX + 5];

void dfs1(int node)
{
    d[node] = 1;

    for(auto it : g[node])
        if(!d[it])
            dfs1(it);

    rev[++k] = node;
}

void dfs2(int node)
{
    d[node] = 0;
    ctc[q].push_back(node);

    for(auto it : t[node])
        if(d[it] == 1)
            dfs2(it);
}

int main()
{
    fin >> N >> M;

    for(int i = 1; i <= M; i++) {

        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        t[y].push_back(x);

    }

    for(int i = 1; i <= N; i++)
        if(!d[i])
            dfs1(i);

    for(int i = N; i >= 1; i--)
        if(d[rev[i]] == 1)
            {
                q++;
                dfs2(rev[i]);
            }

    fout << q << '\n';

    for(int i = 1; i <= q; i++)
    {
        for(auto it : ctc[i])
            fout << it << ' ';

        fout << '\n';
    }

    return 0;
}