Cod sursa(job #3243074)

Utilizator BOSSSTEFANPetrescu Ioan Stefan BOSSSTEFAN Data 15 septembrie 2024 16:05:39
Problema Componente tare conexe Scor 70
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
using namespace std;
ifstream cin("ctc.in");
ofstream cout("ctc.out");
vector <int> g[100001],rez[100001];
int ok[100001],st[100001],okst[100001],niv[100001],nma[100001],t,k;
void dfs(int nod)
{
    ok[nod]=1;
    okst[nod]=1;
    st[++k]=nod;
    nma[nod]=niv[nod];
    for(auto x : g[nod])
    {
        if(ok[x]==0)
        {
            niv[x]=niv[nod]+1;
            dfs(x);
            nma[nod]=min(nma[nod],nma[x]);
        }
        else
        {
            if(okst[x]==1)
                nma[nod]=min(nma[nod],nma[x]);
        }
    }
    if(nma[nod]==niv[nod])
    {
        t++;
        while(st[k]!=nod)
        {
            rez[t].push_back(st[k]);
            okst[st[k]]=0;
            k--;
        }
        rez[t].push_back(nod);
        okst[nod]=0;
        k--;
    }
}
int main()
{
    int n,m,i,x,y;
    cin>>n>>m;
    for(i=1;i<=m;i++)
    {
        cin>>x>>y;
        g[x].push_back(y);
    }
    for(i=1;i<=n;i++)
    {
        if(ok[i]==0)
            dfs(i);
    }
    cout<<t<<'\n';
    for(i=1;i<=t;i++)
    {
        for(auto x : rez[i])
            cout<<x<<" ";
        cout<<'\n';
    }
    return 0;
}