Cod sursa(job #3295220)

Utilizator StefanRaresStefan Rares StefanRares Data 3 mai 2025 17:14:50
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");
const int NMAX = 1e5 + 5;
int n, m, NrCtc,
    cur_idx = 1,       ///id-ul folosit pentru asocieri
    idx[NMAX],         ///id-ul nodului
    lowlink[NMAX];     ///cel mai mic idx la care pot ajunge
vector<int> G[NMAX],   ///Graful;
       CTC[NMAX]; ///Componente conexe
bool ActivSt[NMAX];
stack<int> st;
void dfs(int nod) ///Tarjan
{
    idx[nod] = cur_idx++;
    lowlink[nod] = idx[nod];
    ActivSt[nod] = 1;
    st.push(nod);
    for(const auto &i : G[nod])
        if(!idx[i])
        {
            dfs(i);
            lowlink[nod] = min(lowlink[nod], lowlink[i]);
        }
        else if(ActivSt[i])
            lowlink[nod] = min(lowlink[nod], lowlink[i]);
    if(lowlink[nod] == idx[nod])
    {
        NrCtc++;
        int crt;
        do
        {
            crt = st.top();
            st.pop();
            CTC[NrCtc].push_back(crt);
            ActivSt[crt] = 0;
        }while(crt != nod);
    }
}
int main()
{
    int i, x, y;
    f >> n >> m;
    for(i = 1; i <= m; ++i)
    {
        f >> x >> y;
        G[x].push_back(y);
    }
    for(i = 1; i <= n; ++i)
        if(!idx[i]) dfs(i);
    g << NrCtc << '\n';
    for(i = 1; i <= NrCtc; i++)
    {
        for(const auto &j : CTC[i])
            g << j << ' ';
        g << '\n';
    }
    f.close();
    g.close();
    return 0;
}