Cod sursa(job #3302436)

Utilizator brianabucur11Briana Bucur brianabucur11 Data 7 iulie 2025 15:15:37
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.18 kb
#include <bits/stdc++.h>

using namespace std;

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

const int nmax=1e5+5;

stack <int> st;
vector <int> g[nmax], gt[nmax], sol[nmax];
int n, m, fr[nmax];

void dfs (int node)
{
    fr[node]=1;
    for (auto it:g[node])
    {
        if (!fr[it])
            dfs(it);
    }
    st.push(node);
}

void dfst (int node, int k)
{
    sol[k].push_back(node);
    fr[node]=0;
    for (auto it:gt[node])
    {
        if (fr[it])
            dfst(it,k);
    }
}

void kosaraju ()
{
    int rez=0;
    for (int i=1; i<=n; i++)
    {
        if (!fr[i])
            dfs(i);
    }
    while (!st.empty())
    {
        int x=st.top();
        st.pop();
        if (fr[x])
        {
            rez++;
            dfst(x,rez);
        }
    }
    fout << rez << '\n';
    for (int i=1; i<=rez; i++)
    {
        for (auto it:sol[i])
            fout << it << " ";
        fout << '\n';
    }
}

signed main()
{
    fin >> n >> m;
    for (int i=1; i<=m; i++)
    {
        int x, y;
        fin >> x >> y;
        g[x].push_back(y);
        gt[y].push_back(x);
    }
    kosaraju();
    return 0;
}