Cod sursa(job #3306705)

Utilizator mihail_11Ionescu Mihail mihail_11 Data 12 august 2025 20:37:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.22 kb
#include <bits/stdc++.h>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
vector<int> graf[100005],rgraf[100005];
int t[100005],ctcon;
vector<int> solutie[100005],toposort;
bool cycle;
void dfs(int nod)
{
    t[nod]=1;
    for(auto a:graf[nod])
    {
        if(t[a]==0)
        {
            dfs(a);
        }
    }
    toposort.push_back(nod);
}
void dfs2(int nod)
{
    t[nod]=0;
    solutie[ctcon].push_back(nod);
    for(auto a:rgraf[nod])
    {
        if(t[a]==1)
        {
            dfs2(a);
        }
    }
}
int main()
{
    int n,m,i,j,nod1,nod2;
    fin>>n>>m;
    for(i=1;i<=m;++i)
    {
        fin>>nod1>>nod2;
        graf[nod1].push_back(nod2);
        rgraf[nod2].push_back(nod1);
    }
    for(i=1;i<=n;++i)
    {
        ///dfs original
        if(t[i]==0)
            dfs(i);
    }
    reverse(toposort.begin(),toposort.end());
    for(auto nod:toposort)
    {
        ///dfs-ul al doilea
        if(t[nod]==1)
        {
            dfs2(nod);
            ++ctcon;
        }
    }
    fout<<ctcon<<'\n';
    for(i=0;i<ctcon;++i)
    {
        for(auto a:solutie[i])
            fout<<a<<' ';
        fout<<'\n';
    }
    return 0;
}