Cod sursa(job #3344389)

Utilizator CheeseEaterHackRoman Alex CheeseEaterHack Data 1 martie 2026 22:02:02
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.42 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, a, b, disc[100001], low[100001];
vector<int> graf[100001], rez[100001];
stack<int> st;
bool inStack[100001];
int timer=0, cnt;

void dfs(int nod)
{
    timer++;//timp cand bagam nodul in stack
    disc[nod]=low[nod]=timer;
    st.push(nod);
    inStack[nod]=true;
    for (int u: graf[nod])
    {
        if (disc[u]==0)//daca nu l-am bagat inca
        {
            dfs(u);
            low[nod]=min(low[nod], low[u]);
        }
        else if (inStack[u])
        {
            low[nod]=min(low[nod], disc[u]);
        }
    }
    if (low[nod]==disc[nod])
    {
        cnt++;
        while (true)
        {
            int nd=st.top();
            st.pop();
            inStack[nd]=false;
            rez[cnt].push_back(nd);
            if (nd==nod)
            {
                break;
            }
        }
    }
}

int main()
{
    fin>>n>>m;
    for (int i=1; i<=m; i++)
    {
        fin>>a>>b;
        graf[a].push_back(b);
    }
    for (int i=1; i<=n; i++)
    {
        if (disc[i]==0)
        {
            dfs(i);
        }
    }
    fout<<cnt<<'\n';
    for (int i=1; i<=cnt; i++)
    {
        sort(rez[i].begin(), rez[i].end());
        for (auto u: rez[i])
        {
            fout<<u<<" ";
        }
        fout<<'\n';
    }


    return 0;
}