Cod sursa(job #3204786)

Utilizator Raul_AArdelean Raul Raul_A Data 17 februarie 2024 14:20:31
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
#define ll long long
#define ld long double
#define eb emplace_back
#define pii pair<int, int>
#define tpl tuple<int, int, int>
#define oo 0x3f3f3f3f
using namespace std;

const string fn("ctc");

ifstream in(fn + ".in");
ofstream out(fn + ".out");

#define cin in
#define cout out

const int MAX = 1e5;

int n, m;
vector<int> g[MAX + 5], gt[MAX + 5], s, ans;
vector<vector<int>> ctc;
bitset<MAX + 5> viz;

void read()
{
    cin >> n >> m;

    for (int i = 1, x, y; i <= m; i++)
    {
        cin >> x >> y;
        g[x].eb(y);
        gt[y].eb(x);
    }
}

void dfs(int node)
{
    viz[node] = 1;
    for (auto x : g[node])
        if (!viz[x])
            dfs(x);

    s.eb(node);
}

void dfst(int node)
{
    viz[node] = 0;
    ans.eb(node);
    for (auto x : gt[node])
        if (viz[x])
            dfst(x);
}

int main()
{
    read();
    for (int i = 1; i <= n; i++)
        if (!viz[i])
            dfs(i);

    while (!s.empty())
    {
        int node = s.back();
        s.pop_back();

        if (viz[node])
        {
            dfst(node);
            sort(ans.begin(), ans.end());
            ctc.eb(ans);

            ans.clear();
        }
    }

    cout << ctc.size() << '\n';
    for (auto it : ctc)
    {
        for (auto x : it)
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}