Cod sursa(job #3030282)

Utilizator GoofyAhBalea Gabriel GoofyAh Data 17 martie 2023 16:29:55
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.16 kb
#include <bits/stdc++.h>

using namespace std;

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

int n, m, id ,ctc, root[100001], viz[100001], in_st[100001];
vector <int> graf[100001];
vector <int> CTC[100001];
stack <int> st;

void citire() {
    int x, y;
    fin >> n >> m;
    for (int i = 1 ; i <= m ; i++) {
        fin >> x >> y;
        graf[x].push_back(y);
    }
}

void dfs(int nod){
    int aux;
    st.push(nod);
    in_st[nod]=1;
    id++;
    viz[nod]=id;
    root[nod]=id;
    for (int el: graf[nod]) {
        if  (viz[el]==0) dfs(el);
        if (in_st[el]) root[nod]=min(root[nod],root[el]);
    }
    if (viz[nod]==root[nod]) {
        while (!st.empty()) {
            aux=st.top();
            CTC[ctc].push_back(aux);
            st.pop();
            in_st[aux]=0;
            root[aux]=viz[aux];
            if (aux==nod) break;
        }
        ctc++;
    }
}

int main(){
    citire();
    for (int i=1;i<=n;i++){
        if (viz[i]==0) dfs(i);
    }
    fout << ctc;
    for (int i=0;i<=ctc;i++) {
        fout << "\n";
        for (int j:CTC[i]) {
            fout << j << " ";
        }
    }
}