Cod sursa(job #3030907)

Utilizator ChocoLupse Ioan Victor Choco Data 17 martie 2023 22:55:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.15 kb
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");

int n,m,viz[100005],nr_CTC;
vector<int>L[100005],LT[100005],LTC[100005];
stack<int>st;

void dfs(int x){
    viz[x] = 1;
    int nr = L[x].size();
    for(int i = 0; i < nr; i++){
        if(!viz[L[x][i]])
            dfs(L[x][i]);
    }
    st.push(x);
}

void dfs2(int x){
    viz[x] = 2;
    LTC[nr_CTC].push_back(x);

    int nr = LT[x].size();
    for(int i = 0; i < nr; i++){
        if(viz[LT[x][i]] == 1)
            dfs2(LT[x][i]);
    }
}

int main()
{
    in >> n >> m;
    for(int i = 1; i <= m; i++){
        int a,b;
        in >> a >> b;
        L[a].push_back(b);
        LT[b].push_back(a);
    }
    for(int i = 1; i <= n; i++)
        if(!viz[i])
            dfs(i);

    while(!st.empty()){
        int nod = st.top();
        st.pop();
        if(viz[nod]==1){
            nr_CTC++;
            dfs2(nod);
        }
    }
    out << nr_CTC << "\n";
    for(int i = 1; i <= nr_CTC; i++,out << "\n")
        for(int j = 0; j < LTC[i].size(); j++)
            out << LTC[i][j] << " ";
    return 0;
}