Cod sursa(job #3153987)

Utilizator alexlazuLazureanu Alexandru Ioan alexlazu Data 2 octombrie 2023 17:01:23
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

const int N = 1e5 + 1;

vector<vector<int>> v(N) , reverse_v (N);
stack <int> S;
int viz[N] , ranc[N];
int n, m;

void read_me()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
    {
        int l1, l2;
        in >> l1 >> l2;
        v[l1].push_back(l2);
        reverse_v[l2].push_back(l1);
    }
}

void dfp(int nod)
{
    viz[nod] = 1;
    for (auto& i : v[nod])
    {
        if (viz[i] == 0)
            dfp(i);
    }
    S.push(nod);
}

void dfm(int nod , int value)
{
    ranc[nod] = value;
    for (auto& i : reverse_v[nod])
    {
        if (ranc[i] == -1)
            dfm(i, value);
    }
}

int main(void)
{
    read_me();
    for (int i = 1; i <= n; i++)
        viz[i] = 0, ranc[i] = -1;
    for (int i = 1; i <= n; i++)
    {
        if(viz[i] == 0)
            dfp(i);
    }
    int val = 0;
    while (!S.empty())
    {
        if (ranc[S.top()] == -1) {
            dfm(S.top(), ++val);
            v[val].clear();
        }
        S.pop();
    }
    for (int i = 1; i <= n; i++)
    {
        v[ranc[i]].push_back(i);
    }
    out << val << '\n';
    for (int j = 1; j <= val; j++)
    {
        for (auto& i : v[j])
        {
            out << i << ' ';
        }
        out << '\n';
    }
    return 0;
}