Cod sursa(job #3274325)

Utilizator Nasa1004Ema Nicole Gheorghe Nasa1004 Data 6 februarie 2025 12:26:25
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.86 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;
const int NMAX = 100002;

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

int cnt = 0; ///al cat-elea intra in stiva
vector <vector <int>> v, ctc;
int f[NMAX]; ///0- nevazut inca, 1-vazut, 2-in ctc
int sus[NMAX];
stack <int> s;
void dfs(int start) {
    int orig = cnt; ///nivelul original
    //cout << start << " " << niv << '\n';
    f[start] = 1;
    sus[start] = cnt;
    s.push(start);
    for(auto nod : v[start]) {
        if(f[nod] == 2)
            continue;

        if(!f[nod]) { ///AVEM copil si unde sa ne ducem
            cnt++;
            dfs(nod);
        }
        sus[start] = min(sus[start], sus[nod]); ///min ca il vrem pe ala cel mai de SUS
    }
    if(sus[start] == orig) { ///nu ne putem duce mai sus
        //cout << "ctc " << start << '\n';
        ctc.push_back(vector <int>());
        while(!s.empty() && s.top() != start) {
            ctc.back().push_back(s.top());
            f[s.top()] = 2;
            //cout << s.top() << " ";
            s.pop();
        }
        //cout << start << '\n';
        s.pop();
        f[start] = 2;
        ctc.back().push_back(start);
    }
}

int main()
{
    int n, m;
    cin >> n >> m;
    v.resize(n + 1);
    for(int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
    }
    /*for(int i = 1; i <= n; i++) {
        cout << "nodul " << i << '\n';
        for(auto var : v[i])
            cout << var << " ";
        cout << '\n';
    }*/
    for(int i = 1; i <= n; i++) {
        if(!f[i]) {
            cnt++;
            dfs(i);
        }
    }
    cout << ctc.size() << '\n';
    for(int i = 0; i < ctc.size(); i++) {
        for(auto var : ctc[i])
            cout << var << " ";
        cout << '\n';
    }
    return 0;
}