Cod sursa(job #3346572)

Utilizator mihai.25Calin Mihai mihai.25 Data 14 martie 2026 12:21:01
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.56 kb
#include <fstream>

#include <vector>

#include <stack>

using namespace std;

vector<vector<int>> G, GT;

vector<bool> visited;

stack<int> s;

vector<int> scc;

void dfs(int node) {

    visited[node] = true;

    for (int next : G[node])
        if (!visited[next])
            dfs(next);
    
    s.push(node);
}

void dfs2(int node, int cnt) {

    visited[node] = true;

    scc[node] = cnt;

    for (int next : GT[node])
        if (!visited[next])
            dfs2(next, cnt);
}

int main() {

    // ios_base :: sync_with_stdio(false);

    // cin.tie(nullptr);

    ifstream cin("ctc.in");

    ofstream cout("ctc.out");

    int n, m;

    cin >> n >> m;

    G.resize(n + 1); 
    
    GT.resize(n + 1); 
    
    visited.resize(n + 1); 
    
    scc.resize(n + 1);

    for (int i = 1; i <= m; ++i) {

        int a, b;

        cin >> a >> b;

        G[a].push_back(b);

        GT[b].push_back(a);
    }

    for (int i = 1; i <= n; ++i)
        if (!visited[i])
            dfs(i);
    
    visited.assign(n + 1, false);

    int cnt = 0;

    while (!s.empty()) {

        int node = s.top();

        s.pop();

        if (!visited[node]) {

            cnt++;

            dfs2(node, cnt);
        }
    }

    vector<vector<int>> ans(cnt + 1);

    for (int i = 1; i <= n; ++i)
        ans[scc[i]].push_back(i);

    cout << cnt << '\n';

    for (int i = 1; i <= cnt; ++i, cout << '\n')
        for (int node : ans[i])
            cout << node << ' ';
    
    return 0;
}