Cod sursa(job #3301359)

Utilizator Tudor_CCTudor Cocu Tudor_CC Data 25 iunie 2025 12:41:18
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <bits/stdc++.h>

using namespace std;

int n,m,x,y;

set <int> s[100005];

vector <int> v[100005];

bool stv[100005];

int in[100005]; ///index non
int ll[100005]; ///low link

int glb=0,cnt=0;

vector <int> st;

void trj(int k)
{
    ++glb;
    in[k]=glb;
    ll[k]=glb;
    stv[k]=1;
    st.push_back(k);
    for(auto a:s[k])
    {
        if(in[a]==-1)
        {
            trj(a);
            ll[k]=min(ll[k],ll[a]);
        }
        else if(stv[a])
        {
            ll[k]=min(ll[k],in[a]);
        }
    }
    if(ll[k]==in[k])
    {
        ++cnt;
        for(int i=st.size()-1;i>=0;i=st.size()-1)
        {
            v[cnt].push_back(st[i]);
            stv[st[i]]=0;
            if(st[i]==k)
            {
                st.pop_back();
                break;
            }
            st.pop_back();
        }
        sort(v[cnt].begin(),v[cnt].end());
    }
}

int main()
{
    ifstream cin("ctc.in");
    ofstream cout("ctc.out");
    cin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        cin>>x>>y;
        s[x].insert(y);
    }
    for(int i=1;i<=n;++i)
    {
        in[i]=-1;
        ll[i]=-1;
    }
    for(int i=1;i<=n;++i)
    {
        if(in[i]==-1)
        {
            trj(i);
        }
    }
    cout<<cnt<<"\n";
    for(int i=1;i<=cnt;++i)
    {
        for(int h=0;h<v[i].size();++h)
        {
            cout<<v[i][h]<<" ";
        }
        cout<<"\n";
    }
    return 0;
}