Cod sursa(job #3295229)

Utilizator altomMirel Fanel altom Data 3 mai 2025 17:50:21
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n, m, i, a, b;
vector<int> v1[100005], v2[100005], l, sol[100005];
int vaz[100005];

void kosaraju1(int nod){
    vaz[nod]=1;
    l.push_back(nod);
    for(int i=0;i<v1[nod].size();i++){
        if(vaz[v1[nod][i]]==0)
            kosaraju1(v1[nod][i]);
    }
    //l.push_back(nod);
}

void kosaraju2(int nod, int rad){
    vaz[nod]=1;
    sol[rad].push_back(nod);
    for(int i=0;i<v2[nod].size();i++){
        if(vaz[v2[nod][i]]==0)
            kosaraju2(v2[nod][i], rad);
    }
}

int main()
{
    fin>>n>>m;

    for(i=1;i<=m;i++){
        fin>>a>>b;

        v1[a].push_back(b);
        v2[b].push_back(a);
    }

    for(i=1;i<=n;i++){
        if(vaz[i]==0){
            kosaraju1(i);
        }
    }

    for(i=1;i<=n;i++){
        vaz[i]=0;
    }

    for(i=0;i<l.size();i++){
        if(vaz[i]==0){
            kosaraju2(l[i], l[i]);
        }
    }


    int cnt=0;
    for(i=1;i<=n;i++){
        if(sol[i].size()>=1){
            cnt++;
        }
    }
    fout<<cnt<<'\n';

    for(i=1;i<=n;i++){
        if(sol[i].size()>=1){
            for(int j=0;j<sol[i].size();j++){
                fout<<sol[i][j]<<" ";
            }
            fout<<'\n';
        }
    }



    return 0;
}