Cod sursa(job #3376983)

Utilizator JenJenCristache Ion JenJen Data 20 noiembrie 2026 22:05:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <fstream>
#include <vector>
#include <bitset>
using namespace std;

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

int n, m;
vector <int> adj[100005];
vector <int> adj_inv[100005];
bitset <100005> ok;

vector <int> st;
vector <int> rez[100005];
int k;
int u, v;

void dfs(int nod, vector <int> adjj[100005], vector<int>& stt)
{
    ok[nod] = 1;
    for (const auto& x : adjj[nod])
    {
        if (!ok[x])
        {
            dfs(x, adjj, stt);
        }
    }

    stt.push_back(nod);
}
int main()
{
    cin >> n >> m;

    for (int i = 1; i <= m; i++)
    {
        cin >> u >> v;
        adj[u].push_back(v);
        adj_inv[v].push_back(u);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!ok[i])
        {
            dfs(i, adj, st);
        }
    }

    ok.reset();

    for (int i = st.size() - 1; i >= 0; i--)
    {
        if (!ok[st[i]])
        {
            dfs(st[i], adj_inv, rez[k++]);
        }
    }

    cout << k << '\n';
    for (int i = 0; i < k; i++)
    {
        for (int j = 0; j < rez[i].size(); j++)
        {
            cout << rez[i][j] << " ";
        }
        cout << '\n';
    }
    return 0;
}