Cod sursa(job #3226655)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 22 aprilie 2024 14:06:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.13 kb
#include <iostream>
#include <bitset>
#include <vector>
using namespace std;

const int INF = 1e9 + 69;
const int MOD = 666013;
const int MAX = 1e5 + 2;

bitset<MAX> ok;
vector<int> comp[MAX];
vector<int> adjB[MAX];
vector<int> adj[MAX];
vector<int> sortTop;
int n, m;
int no;

void dfs(int nod, vector<int> adj[MAX], vector<int> &v) {
    ok[nod] = 1;
    for(const int &x : adj[nod])
        if(!ok[x])
            dfs(x, adj, v);
    v.push_back(nod);
}

signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);


    freopen("ctc.in", "r", stdin);
    freopen("ctc.out", "w", stdout);


    cin >> n >> m;

    int x, y;
    for(int i = 0; i < m; i++) {
        cin >> x >> y;
        adj[x].emplace_back(y);
        adjB[y].emplace_back(x);
    }

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

    ok = 0;
    for(int i = sortTop.size() - 1; i >= 0; i--)
        if(!ok[sortTop[i]])
            dfs(sortTop[i], adjB, comp[no++]);

    cout << no << '\n';
    for(int i = 0; i < no; i++) {
        for(const int& x : comp[i])
            cout << x << ' ';
        cout << '\n';
    }
    return 0;
}