Cod sursa(job #3040231)

Utilizator LucaMuresanMuresan Luca Valentin LucaMuresan Data 29 martie 2023 16:19:49
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <bits/stdc++.h>

using namespace std;

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

const int NMAX = 1e5;

vector<int>g[NMAX + 5], rev[NMAX + 5];
bitset<NMAX + 5>vis;
vector<vector<int>>comp;
vector<int>ord, curr;

void dfs1 (int u)
{
    vis[u] = true;
    for (const auto &v : g[u])
    {
        if (!vis[v])
            dfs1(v);
    }
    ord.push_back(u);
}

void dfs2 (int u)
{
    vis[u] = true;
    curr.push_back(u);
    for (const auto &v : rev[u])
    {
        if (!vis[v])
            dfs2(v);
    }
}

int main()
{
    int n, m;
    in >> n >> m;

    while (m--)
    {
        int u, v;
        in >> u >> v;
        g[u].push_back(v);
        rev[v].push_back(u);
    }

    dfs1(1);
    reverse(ord.begin(), ord.end());

    vis = 0;

    for (int i=1; i<=n; i++)
    {
        if (!vis[i])
        {
            curr.clear();
            dfs2(i);
            comp.push_back(curr);
        }
    }

    out << (int) comp.size() << '\n';
    for (auto &v : comp)
    {
        sort(v.begin(), v.end());
        for (const auto &u : v)
            out << u << ' ';
        out << '\n';
    }


    return 0;
}