Cod sursa(job #3362287)

Utilizator Mihai09Mihai Arteni Mihai09 Data 5 august 2026 15:40:59
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n,m,id[100010],lowlink[100010],indx=1,nr;
list <int>adj[100010],scc[100010];
bool visited[100010],ons[100010];
stack <int>st;

void tarjan(int x)
{
    id[x] = indx;
    indx++;
    lowlink[x] = id[x];
    ons[x] = 1;
    st.push(x);
    
    for(int s:adj[x])
    {
        if(id[s] == 0)
        {
            tarjan(s);
            lowlink[x] = min(lowlink[x],lowlink[s]);
        }
        else if(ons[s])
        {
            lowlink[x] = min(lowlink[x],lowlink[s]);
        }
    }
    
    if(id[x] == lowlink[x])
    {
        nr++;
        while(1)
        {
            int w = st.top();
            scc[nr].push_back(w);
            ons[w] = 0;
            st.pop();
            if(x == w)
            {
                break;
            }
        }
    }
}

int main()
{
    fin >>n >>m;
    for(int i = 1;i <= m;i++)
    {
        int a,b;
        fin >>a >>b;
        adj[a].push_back(b);
    }
    for(int i = 1;i <= n;i++)
    {
        if(id[i] == 0)
        {
            tarjan(i);
        }
    }
    fout <<nr<<"\n";
    for(int i = 1;i <= nr;i++)
    {
        for(int s:scc[i])
        {
            fout <<s<<" ";
        }
        fout <<"\n";
    }
    return 0;
}