Cod sursa(job #2829288)

Utilizator rafaelrafyChitan Rafael rafaelrafy Data 8 ianuarie 2022 14:21:26
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.33 kb
#include <vector>
#include <stack>
#include <algorithm>
#include <fstream>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
stack<int>st;
vector<int>comp[100010];
int ct=0,nrc,viz[100010],pe_stiva[100010],L[100010],Lmax;
int id[100010],id_initial[100010];//id-indicele minim, id_initial-primul indice
int m,n,x,y;
vector<int>v[110];
void dfs(int x)
{
    id[x]=id_initial[x]=++ct;
    viz[x]=pe_stiva[x]=1;
    st.push(x);
    for(auto &it:v[x])
    {
        if(viz[it] && pe_stiva[it])
            id[x]=min(id[x],id[it]);
        else if(!viz[it])
        {
            dfs(it);
            if(pe_stiva[it])
                id[x]=min(id[x],id[it]);
        }
    }
    if(id[x]==id_initial[x])
    {
        nrc++;
        while(st.top()!=x)
        {
            L[nrc]++;
            comp[nrc].push_back(st.top());
            pe_stiva[st.top()]=0;
            st.pop();
        }
        L[nrc]++;
        comp[nrc].push_back(st.top());
        pe_stiva[st.top()]=0;
        st.pop();
    }
}
int main() {
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x>>y;
        v[x].push_back(y);
    }
    for(int i=1;i<=n;i++)
    {
        if(!viz[i])
            dfs(i);
    }
    cout<<nrc<<'\n';
    for(int i=1;i<=nrc;i++)
    {
        for(auto it:comp[i])
            cout<<it<<' ';
        cout<<'\n';
    }
    return 0;
}