Cod sursa(job #2928557)

Utilizator radubuzas08Buzas Radu radubuzas08 Data 23 octombrie 2022 12:59:32
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
// CTC - TARJAN
// Created by Radu Buzas on 22.10.2022.
//

#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
using namespace std;

#define min(a, b)  ( (a < b) ? a : b)

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

int incide = 1;

void dfs(vector<vector<int>> & graph, vector<int> & id, vector<int> & low, stack<int> & s, vector<bool> &inStack, vector<vector<int>> & sol, int k){
    inStack[k] = true;
    low[k] = id[k] = incide++;
    s.push(k);
    for (auto x : graph[k]) {
        if(!id[x])
            dfs(graph, id, low, s, inStack, sol, x), low[k] = min(low[k], low[x]);
        else if(inStack[x])
            low[k] = min(low[k], low[x]);
    }
    if(id[k] == low[k]){
        vector<int> tmp;
        while(s.top() != k)
            inStack[s.top()] = 0, tmp.push_back(s.top()) , s.pop();
        inStack[s.top()] = 0, tmp.push_back(s.top()), s.pop();
        sol.push_back(tmp);
        tmp.clear();
    }
}

int main(){
    int n, m, x, y;
    in >> n >> m;
    vector<vector<int>> graph(n +1), sol;
    vector<int> id(n+1, 0), low(n+1, 0);
    vector<bool> boolV(n+1, 0);
    stack<int> s;
    while(m--){
        in >> x >> y;
        graph[x].push_back(y);
    }
    in.close();

    for(int i = 1; i <= n; i++)
        if(!id[i])
            dfs(graph, id, low,s, boolV, sol, i);

    out << sol.size() << '\n';
    for (auto x : sol) {
        sort(x.begin(), x.end());
        for (auto y: x) {
            out << y << ' ';
        }
        out << '\n';
    }

    return 0;
}