Cod sursa(job #3285000)

Utilizator Dragono63Stanciu Rares Stefan Dragono63 Data 12 martie 2025 13:48:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#ifndef LOCAL
    #pragma GCC optimize("O3")
    // #pragma GCC target("avx2")
#endif

#ifdef LOCAL
    #define _GLIBCXX_DEBUG
#endif

#include <bits/stdc++.h>
#define pb push_back
#define pii pair<int, int>
using ll = long long;
using ci = const int;
using cll = const long long;

using namespace std;

const int NMAX = 1e5 + 5;
/*******************************/
// INPUT / OUTPUT

#ifndef LOCAL
    ifstream in("ctc.in");
    ofstream out("ctc.out");
    #define cin in
    #define cout out
#endif
/*******************************/
/// GLOBAL DECLARATIONS

int N, M;
int cnt;
int vis[NMAX], col[NMAX];

vector <int> topo;
vector <int> adj[NMAX], inv[NMAX], ctcs[NMAX];
/*******************************/
/// FUNCTIONS

void ReadInput();
void Solution();
void Output();
/*******************************/
///-------------------------------------
inline void ReadInput()
{
    cin >> N >> M;

    int x, y;
    for (int i = 0 ; i < M ; ++ i)
    {
        cin >> x >> y;
        adj[x].push_back(y);
        inv[y].push_back(x);
    }
}
///-------------------------------------
inline void dfs1(int node)
{
    if (vis[node]) return;

    vis[node] = true;
    for (auto u: adj[node])
        dfs1(u);

    topo.push_back(node);
}
///-------------------------------------
inline void dfs2(int node)
{
    if (col[node]) return;

    col[node] = cnt;
    for (auto u: inv[node])
        dfs2(u);
}
///-------------------------------------
inline void Solution()
{
    for (int node = 1 ; node <= N ; ++ node)
        dfs1(node);

    reverse(topo.begin(), topo.end());
    for (auto node: topo)
    {
        if (!col[node])
        {
            cnt ++;
            dfs2(node);
        }
    }

    for (int node = 1 ; node <= N ; ++ node)
        ctcs[col[node]].push_back(node);
}
///-------------------------------------
inline void Output()
{
    cout << cnt << "\n";
    for (int i = 1 ; i <= cnt ; ++ i)
    {
        for (auto node: ctcs[i]) cout << node << " ";
        cout << "\n";
    }
}
///-------------------------------------
int main()
{
    #ifndef LOCAL
        ios::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);
    #endif
    ReadInput();
    Solution();
    Output();
    return 0;
}