Cod sursa(job #3213908)

Utilizator AlexInfoIordachioaiei Alex AlexInfo Data 13 martie 2024 16:42:20
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>

using namespace std;

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

#define pii pair<int, int>
#define pb push_back
#define fi first
#define se second
typedef long long ll;

const int NMAX = 1e5 + 30;
const int INF = 0x3f3f3f3f;

int n, m, x, y, v[NMAX], nrctc;
vector<vector<int>> graf(NMAX), gt(NMAX);
vector<int> fin;
vector<vector<int>> ctc(NMAX);

void read()
{
    in >> n >> m;
    for (int i = 1; i <= m; i++)
        in >> x >> y, graf[x].pb(y), gt[y].pb(x);
}

void dfs(int node)
{
    if (!nrctc)
    {
        v[node] = 1;
        for (auto to : graf[node])
            if (!v[to])
                dfs(to);

        fin.pb(node);
        return;
    }
    // nrctc>=1
    v[node] = 1;
    ctc[nrctc].pb(node);
    for (auto to : gt[node])
        if (!v[to])
            dfs(to);
}

void solve()
{
    for (int i = 1; i <= n; i++)
        if (!v[i])
            dfs(i);

    memset(v, 0, sizeof v);

    reverse(fin.begin(), fin.end());
    for (auto node : fin)
        if (!v[node])
        {
            nrctc++;
            dfs(node);
        }

    out << nrctc << '\n';
    for (int i = 1; i <= nrctc; i++, out << '\n')
        for (auto node : ctc[i])
            out << node << ' ';
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    ios::sync_with_stdio(false);

    read();
    solve();

    return 0;
}