Cod sursa(job #3344444)

Utilizator BidonTurtitBezdedan Eric BidonTurtit Data 1 martie 2026 23:27:57
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.41 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>
#include <bitset>
#define NMax 100005
using namespace std;

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

int n, m, sol=0;
vector <int> CTC[NMax];
vector <int> vecini[NMax];
 bitset <NMax> v;
 stack <int> temp;
 vector <int> vecini_t[NMax];

void dfs1(int start)
{
    v[start]=1;
    for(auto nod: vecini[start])
    {
        if(v[nod]==0)
            dfs1(nod);
    }
    temp.push(start);
}

void dfs2(int start)
{
    v[start]=1;
    CTC[sol].push_back(start);
    for(auto nod: vecini_t[start])
    {
        if(v[nod]==0)
            dfs2(nod);
    }
}

void kasaraju()
{
    for(int i=1;i<=n;i++)
    {
        if(v[i]==0)
            dfs1(i);
    }
    for(int i=1;i<=n;i++)
    {
        for(auto nod: vecini[i])
        {
            vecini_t[nod].push_back(i);
        }
    }
    v.reset();
    while(!temp.empty())
    {
        int a=temp.top();
        temp.pop();
        if(v[a]==0)
        {
            sol++;
            dfs2(a);

        }

    }
}

int main()
{
    fin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x,y;
        fin>>x>>y;
        vecini[x].push_back(y);
    }
    kasaraju();
    fout<<sol<<"\n";
    for(int i=1;i<=sol;i++)
    {
        for(auto i: CTC[i])
            fout<<i<<" ";
        fout<<"\n";
    }
    return 0;
}