Cod sursa(job #2227739)

Utilizator ContDeRacistAliniateEBlat ContDeRacist Data 1 august 2018 16:59:35
Problema Componente tare conexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.14 kb
#include <fstream>
#include <vector>

using namespace std;

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

const int N = 1e5 + 7;

vector < vector < int > > v;

vector < int > adia1[N], adia2[N], p, aux;

bool f[N];

void order(int x) {
    f[x] = 1;
    for (auto i : adia1[x])
        if (!f[i])
            order(i);
    p.push_back(x);
}

void stabb(int x, vector < int > & comp) {
    comp.push_back(x);
    f[x] = 0;
    for (auto i : adia2[x])
        if (f[i])
            stabb(i, comp);
}

int main()
{
    int n, m, a, b;
    cin >> n >> m;
    while (m--) {
        cin >> a >> b;
        adia1[a].push_back(b);
        adia2[b].push_back(a);
    }
    for (int i = 1; i <= n; ++i)
        if (!f[i])
            order(i);

    int comp(0);

    for (int i = 0; i < n; ++i) {
        int nod = p[i];
        if (f[nod])
            aux.clear(),
            stabb(nod, aux),
            v.push_back(aux);
    }
    cout << v.size() << "\n";
    for (int i = 0; i < v.size(); ++i) {
        for (auto it : v[i])
            cout << it << ' ';

        cout << '\n';
    }
    return 0;
}