Cod sursa(job #2928828)

Utilizator David_PatranjelDavid Patranjel David_Patranjel Data 23 octombrie 2022 22:35:37
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.43 kb
///Problema 4 O(n + m) - Tarjan
///Link:
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <unordered_map>

using namespace std;

vector<vector<int>> lista;
vector<int> viz,ids,lw;
vector<bool> st;
stack<int> stiva;
int contor = 1, cc = 1;
unordered_map<int, vector<int>> ccs;

void DFS(int nod){
    ids[nod] = contor++;
    lw[nod] = ids[nod];
    viz[nod] = 1;
    st[nod] = true;
    stiva.push(nod);
    for(auto& i:lista[nod]){
        if(!viz[i]){
            DFS(i);
        }
        if(st[i])
            lw[nod] = min(lw[nod], lw[i]);
    }

    if(ids[nod] == lw[nod]){
        int popped;
        vector<int> aux;
        do{
            popped = stiva.top();
            stiva.pop();
            st[popped] = false;
            aux.push_back(popped);
        }while(popped != nod);
        ccs[cc++] = aux;
    }
}

int main()
{
    int n,m,x,y;
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin>>n>>m;
    lista.resize(n+1);
    for(int i = 1; i <= m; i++){
        fin>>x>>y;
        lista[x].push_back(y);
    }

    viz.resize(n+1, 0);
    st.resize(n+1, false);
    ids.resize(n+1, 0);
    lw.resize(n+1, 0);

    DFS(1);

    fout<<cc - 1<<endl;
    for(int i = 1; i < cc; i++){
        for(auto& j:ccs[i]){
            fout<<j<<" ";
        }
        fout<<endl;
    }
    fin.close();
    fout.close();
    return 0;
}