Cod sursa(job #3310714)

Utilizator alesiodemiriAlesio Demiri alesiodemiri Data 15 septembrie 2025 22:44:06
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2 kb
#include <iostream>
#include <queue>
#include <algorithm>
#include <set>
#include <map>
#include <stack>
#include <vector>
#include <string>
#include <deque>
#include <unordered_map>
#include <unordered_set>
#include <cmath>
#include <iomanip>

using namespace std;

#define ll long long

int n;
int m;
vector<vector<int>> graph;
int id = 0;
int sccCount = 0;
vector<int> ids, low;
vector<bool> onStack;
stack<int> stk;

void ReadData() {
    cin >> n >> m;
    graph.resize(n, vector<int>());
    for(int i = 0; i < m; i++){
        int start, end;
        cin >> start >> end;
        start--; end--;
        graph[start].push_back(end);
    }
    ids.resize(n , -1);
    low.resize(n, 0);
    onStack.resize(n, false);
}

void dfs(int at){
    stk.push(at);
    onStack[at] = true;
    ids[at] = low[at] = id++;
    for(int neighbor: graph[at]){
        if(ids[neighbor] == -1)
            dfs(neighbor);
        if(onStack[neighbor])
            low[at] = min(low[at], low[neighbor]);
    }
    if(ids[at] == low[at]){
        while (true) {
            int node = stk.top();
            stk.pop();
            onStack[node] = false;
            low[node] = ids[at];
            if (node == at) break;
        }
        sccCount++;
    }
}

void Solve() {
    for(int i = 0; i < n; i++){
        if(ids[i] == - 1)
            dfs(i);
    }

    unordered_map<int, vector<int>> result;
    for(int i = 0; i < n; i++){
        result[low[i]].push_back(i + 1);
    }
    vector<vector<int>> ssc;

    for (const auto& [key, value] : result) {
        ssc.push_back(value);
    }
    cout << ssc.size() << "\n";
    for(vector<int>& values: ssc){
        for(int val: values)
            cout << val << " ";
        cout << "\n";
    }
    cout << "\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    int t = 1;
    // cin >> t; // Uncomment for multiple test cases
    while (t--) {
        ReadData();
        Solve();   
    }
    return 0;
}