Cod sursa(job #3361383)

Utilizator Zeno1789Zeno Ciuca Zeno1789 Data 23 iulie 2026 17:18:42
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <fstream>
#include <vector>
#define int long long
using namespace std;

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

int n,m;
vector<int> adj[100005],rev_adj[100005],order;
bool visited[100005];
vector<vector<int>> scc;

void dfs1(int node) {
    visited[node]=true;
    for (int neighbor:adj[node]) {
        if (!visited[neighbor]) {
            dfs1(neighbor);
        }
    }
    order.push_back(node);
}

void dfs2(int node,vector<int>& component) {
    visited[node]=true;
    component.push_back(node);
    for (int neighbor:rev_adj[node]) {
        if (!visited[neighbor]) {
            dfs2(neighbor,component);
        }
    }
}

signed main() {
    cin>>n>>m;
    for (int i=0; i<m; ++i) {
        int u,v;
        cin>>u>>v;
        adj[u].push_back(v);
        rev_adj[v].push_back(u);
    }
    for (int i=1; i<=n; ++i) {
        if (!visited[i]) {
            dfs1(i);
        }
    }
    for (int i=1; i<=n; ++i) {
        visited[i]=false;
    }
    for (int i=n-1; i>=0; --i) {
        int node=order[i];
        if (!visited[node]) {
            vector<int> component;
            dfs2(node,component);
            scc.push_back(component);
        }
    }
    cout<<scc.size()<<"\n";
    for (const auto& component:scc) {
        for (int i=0; i<(int)component.size(); ++i) {
            cout<<component[i]<<(i==(int)component.size()-1?"":" ");
        }
        cout<<"\n";
    }
}