Cod sursa(job #3265674)

Utilizator Octa-pe-infoNechifor Octavian Octa-pe-info Data 2 ianuarie 2025 13:28:15
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 kb
#include <iostream>
#include <vector>
#include <stack>
#include <fstream>
using namespace std;

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

vector<vector<int>>tabel,inv,cmp;
stack<int>st;
vector<int>viz;

void dfs(int nod){

    viz[nod] = 1;

    for(auto i : tabel[nod]){

        if(!viz[i]){

            dfs(i);

        }

    }

    st.push(nod);
}

void dfs2(int nod,int cnt){

    cmp[cnt].push_back(nod);
    viz[nod] = 2;

    for(auto i : inv[nod]){

        if(viz[i] == 1){

            dfs2(i,cnt);

        }

    }
}

int main()
{

    int n,m;

    fin>>n>>m;

    tabel.resize(n+1);
    inv.resize(n+1);
    viz.resize(n+1,0);
    cmp.resize(n+1);

    for(int i=1;i<=m;i++){

        int a,b;
        fin>>a>>b;

        tabel[a].push_back(b);
        inv[b].push_back(a);
    }

    for(int i=1;i<=n;i++){

        if(!viz[i]){

            dfs(i);

        }

    }

    int cnt = 0;

    while(!st.empty()){

        if(viz[st.top()] == 1){
            dfs2(st.top(),++cnt);
        }
        st.pop();
    }

    fout<<cnt<<'\n';

    for(int i=1;i<=cnt;i++){

        for(auto j : cmp[i])
            fout<<j<<" ";
        fout<<'\n';
    }

    return 0;
}