Cod sursa(job #3271092)

Utilizator Bolfa_DBolfa Diana Bolfa_D Data 25 ianuarie 2025 10:12:32
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define NMAX 100500
#define ABS 10001000
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int>v[NMAX];
int cost, disc[NMAX], low[NMAX],use[NMAX];
deque<int>ans, q[NMAX],rn ;
void dfs(int node)
{
    disc[node]=++cost;
    low[node]=cost;
    use[node]=1;
    rn.push_back(node);

    for(auto i:v[node])
        if(disc[i]==ABS)
        {
            dfs(i);
            low[node]=min(low[i], low[node]);
        }
        else //if(use[i]==1)
            low[node]=min(low[i], low[node]);

    if(disc[node]==low[node])
    {
        ans.push_back(disc[node]);
        while(!rn.empty() && rn.back()!=node)
        {
            use[rn.back()]=0;
            q[disc[node]].push_back(rn.back());
            rn.pop_back();
        }
        use[node]=0;
        q[disc[node]].push_back(node);
        rn.pop_back();
    }
}

int n,m, x, y;
int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;++i)
    {
        fin>>x>>y;
        v[x].push_back(y);
    }

    for(int i=1;i<=n;++i)
    {
        low[i]=ABS;
        disc[i]=ABS;
    }

    for(int i=1;i<=n;++i)
        if(disc[i]==ABS)
            dfs(i);

    fout<<ans.size()<<'\n';
    for(auto i:ans)
    {
        for(auto j:q[i])
            fout<<j<<" ";
        fout<<'\n';
    }

    return 0;
}