Cod sursa(job #3348973)

Utilizator RaduCalisovCalisovRadu RaduCalisov Data 24 martie 2026 21:25:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.44 kb
#include <bits/stdc++.h>
using namespace std;

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

int n,m;
vector<vector<int>> v;
vector<vector<int>> t;
stack<int> st;
vector<bool> checked;
vector<bool> checkedcomp;
vector<vector<int>> comp;

void dfs(int nod){
    checked[nod] = 1;
    for(int i = 0 ; i<v[nod].size();i++){
        int newnod = v[nod][i];

        if(!checked[newnod])
            dfs(newnod);
    }

    st.push(nod);
}

void dfs_t(int nod,int wcomp){
    comp[wcomp].push_back(nod);
    checkedcomp[nod] = 1;

    for(int i = 0 ; i < t[nod].size() ;i++ ){
        int newnod = t[nod][i];

        if(!checkedcomp[newnod])
            dfs_t(newnod,wcomp);
    }
}

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

    v.resize(n+1);
    t.resize(n+1);
    checked.resize(n+1,0);
    checkedcomp.resize(n+1,0);

    for(int i=1;i<=m;i++){
        int x,y;
        fin>>x>>y;
        v[x].push_back(y);
        t[y].push_back(x);
    }

    for(int i = 1;i<=n;i++){
        if(checked[i] == 0)
            dfs(i);
    }

    while(st.size()){
        int nod = st.top();

        if(!checkedcomp[nod]){
            int wcomp = comp.size();
            comp.emplace_back();

            dfs_t(nod,wcomp);
        }

        st.pop();
    }

    fout<<comp.size()<<"\n";

    for(int i = 0 ; i < comp.size();i++){
        for(auto j : comp[i])
            fout<<j<<" ";
        fout<<"\n";
    }
}