Cod sursa(job #3268956)

Utilizator BogaBossBogdan Iurian BogaBoss Data 18 ianuarie 2025 09:54:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <bits/stdc++.h>
#define NMAX 100000
using namespace std;

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

vector<vector<int>> rez;

vector<int> e[NMAX + 5];
vector<int> st;
int num[NMAX + 5], low[NMAX + 5], on_st[NMAX + 5], cnt = 1;

void tarjan(int node)
{
    low[node] = cnt;
    num[node] = cnt;
    cnt++;
    st.push_back(node);
    on_st[node] = 1;
    for(auto adj : e[node])
    {
        if(num[adj] == 0)
            tarjan(adj);
        if(on_st[adj])
            low[node] = min(low[node],low[adj]);
    }

    if(low[node] == num[node])
    {
        vector<int> rasp;
        while(true)
        {
            int nod = st.back();
            st.pop_back();
            on_st[nod] = 0;
            rasp.push_back(nod);
            if(node == nod) break;
        }
        rez.push_back(rasp);
    }
}

int main()
{
    int n,m;
    fin >> n >> m;
    for(int i = 1; i<= m; i++)
    {
        int x, y;
        fin >> x >> y;
        e[x].push_back(y);
    }
    for(int i = 1; i<=n; i++)
    {
        if(num[i] == 0)
            tarjan(i);
    }
    fout << rez.size() << '\n';
    for(auto v : rez)
    {
        for(auto i : v)
                    fout << i << ' ';
        fout << '\n';
    }
    return 0;
}