Cod sursa(job #2984842)

Utilizator verde.cristian2005Verde Flaviu-Cristian verde.cristian2005 Data 24 februarie 2023 23:53:58
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.2 kb
#include <bits/stdc++.h>
using namespace std;
vector <int> v[100001],afis[100001];
bool vis[100001];
int steve[100001],low[100001],vf;
bool insteve[100001];
int cnt, x;
void dfs(int nod)
{
    low[nod]=++x;
    int aux = x;
    vis[nod]=1;
    insteve[nod]=1;
    steve[++vf]=nod;
    for(auto it:v[nod])
        if(insteve[it])
            low[nod]=min(low[nod],low[it]);
    for(auto it:v[nod])
        if(!vis[it])
        {
            dfs(it);
            low[nod]=min(low[nod],low[it]);
        }
    if(low[nod]==aux)
    {
        ++cnt;
        while(steve[vf]!=nod)
        {
            afis[cnt].push_back(steve[vf]);
            insteve[steve[vf--]]=0;
        }
        afis[cnt].push_back(steve[vf]);
        insteve[steve[vf--]]=0;
    }
}
int main()
{
    freopen("ctc.in","r",stdin);
    freopen("ctc.out","w",stdout);
    int n,m,i,a,b;
    cin>>n>>m;
    for(i=1; i<=m; i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
    }
    for(i=1; i<=n; i++)
        if(!vis[i])
            dfs(i);
    cout<<cnt<<'\n';
    for(i=1; i<=cnt; i++)
    {
        for(auto it:afis[i])
            cout<<it<<" ";
        cout<<'\n';
    }
    return 0;
}