Cod sursa(job #3357941)

Utilizator TestLicenta123Test Test TestLicenta123 Data 13 iunie 2026 22:02:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.11 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

int main() {
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    
    int N, M;
    fin >> N >> M;
    
    vector<vector<int>> adj(N + 1);
    vector<vector<int>> rev_adj(N + 1);
    
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
        rev_adj[y].push_back(x);
    }
    
    vector<bool> visited(N + 1, false);
    stack<int> stk;
    
    for (int i = 1; i <= N; ++i) {
        if (!visited[i]) {
            stack<pair<int, int>> dfs_stk;
            dfs_stk.push({i, 0});
            visited[i] = true;
            while (!dfs_stk.empty()) {
                int u = dfs_stk.top().first;
                int& idx = dfs_stk.top().second;
                if (idx < (int)adj[u].size()) {
                    int v = adj[u][idx++];
                    if (!visited[v]) {
                        visited[v] = true;
                        dfs_stk.push({v, 0});
                    }
                } else {
                    dfs_stk.pop();
                    stk.push(u);
                }
            }
        }
    }
    
    fill(visited.begin(), visited.end(), false);
    vector<vector<int>> sccs;
    
    while (!stk.empty()) {
        int u = stk.top();
        stk.pop();
        if (!visited[u]) {
            vector<int> component;
            stack<int> dfs_stk2;
            dfs_stk2.push(u);
            visited[u] = true;
            while (!dfs_stk2.empty()) {
                int curr = dfs_stk2.top();
                dfs_stk2.pop();
                component.push_back(curr);
                for (int v : rev_adj[curr]) {
                    if (!visited[v]) {
                        visited[v] = true;
                        dfs_stk2.push(v);
                    }
                }
            }
            sccs.push_back(component);
        }
    }
    
    fout << sccs.size() << "\n";
    for (const auto& comp : sccs) {
        for (int node : comp) {
            fout << node << " ";
        }
        fout << "\n";
    }
    
    fin.close();
    fout.close();
    return 0;
}