Cod sursa(job #3300455)

Utilizator iulia_morariuIuli Morariu iulia_morariu Data 15 iunie 2025 23:23:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <algorithm>
#include <iostream>
#include <fstream>
#include <climits>
#include <vector>
#include <stack>
#include <cmath>
// #include <bits/stdc++.h>
#define in  fin
#define out fout

using namespace std;

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

vector<int> g[100001];
int h[100001], niv[100001];
stack<int> st;
int m[100001];
vector< vector<int> > ctc;
int it = 1;

void dfs(int nod){
    st.push(nod);
    m[nod] = 2;
    for(const int &x : g[nod]){
        if(m[x] == 2){
            h[nod] = min(h[nod], niv[x]);
            continue;
        }
        if(m[x]) continue; // transversala skibidi dinaia

        niv[x] = h[x] = ++it;
        dfs(x);
        h[nod] = min(h[nod], h[x]);
    }

    if(h[nod] >= niv[nod]){ // e comp
        // cout << nod << " e 'cap' de componenta\n";
        ctc.push_back({});
        while(st.top() != nod){
            ctc.back().push_back(st.top());
            m[st.top()] = 1;
            st.pop();
        }
        ctc.back().push_back(st.top()); st.pop();
        m[nod] = 1;
    }
}

signed main(){
    ios_base::sync_with_stdio(false);
    in.tie(NULL);

    int n, M; in >> n >> M;
    for(int i = 0; i < M; i++){
        int a, b; in >> a >> b;
        g[a].push_back(b);
    }

    for(int i = 1; i <= n; i++){
        if(!m[i]) dfs(i);
    }

    out << ctc.size() << '\n';
    for(const vector<int> &x : ctc){
        for(const int &y : x) out << y << " ";
        out << '\n';
    }

    return 0;
}