Cod sursa(job #2928697)

Utilizator kanyjmkSabau Eduard kanyjmk Data 23 octombrie 2022 18:00:30
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.09 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
using namespace std;

/*
        Acesta este algoritmul lui Tarjan pentru gasirea componentelor tare conexe intr-un graf orientat. Pentru fiecare nod, ii atribuim un id(ceea ce il va marca ca vizitat si care
    reprezinta practic pozitia sa in permutarea obtinuta dupa parcurgerea DFS), o low-link value(cel mai mic id la care se poate ajunge din acest nod prin dfs, inclusiv nodul) si se 
    adauga pe stiva elementelor. Dupa ce am vizitat toti descendentii nodului urmator, la intoarcerea din recursivitatea, verificam daca nodul este pe stiva si modificam low-link value-ul 
    pentru a o propaga prin toata componenta tare conexa. Dupa ce am vizitat toti descendentii nodului curent, verificam daca id-ul lui este egal cu low-link value-ul, astfel putem stii 
    daca este inceputul unei componente tare conexe si putem construi componenta conexe eliminand nodurile din stiva pana ajungem la nodul respectiv.
        Complexitatea algoritmului este O(n+m) intrucat este un DFS modificat.

*/

ifstream fin("ctc.in");
ofstream fout("ctc.out");
int id = 0;
vector<vector<int>> sccs;
void dfs(int curr_node, int& n, vector<vector<int>>&ad_list, int low_vals[100005], int ids[100005], bool on_stack[100005], stack<int>& scc_stack)
{
    scc_stack.push(curr_node);
    on_stack[curr_node] = true;
    ids[curr_node] = low_vals[curr_node] = id;
    id++;
    for(auto it = ad_list[curr_node].begin(); it < ad_list[curr_node].end(); it++)
    {
        if(ids[*it] == -1)
            dfs(*it, n, ad_list, low_vals, ids, on_stack, scc_stack);
        if(on_stack[*it])
            low_vals[curr_node] = min(low_vals[curr_node], low_vals[*it]);
    }
    if(ids[curr_node] == low_vals[curr_node])
        {
            int node;
            vector<int> scc;
            while(curr_node != scc_stack.top())
            {
                node = scc_stack.top();
                on_stack[node] = false;
                low_vals[node] = ids[curr_node];
                scc.push_back(node);
                scc_stack.pop();
            }while(curr_node != scc_stack.top());

            node = scc_stack.top();
            on_stack[node] = false;
            low_vals[node] = ids[curr_node];
            scc.push_back(node);
            scc_stack.pop();

            sccs.push_back(scc);
        }
}

int main()
{
    int n, m;
    int low_vals[100005];
    int ids[100005];
    bool on_stack[100005];
    stack<int> scc_stack;

    fin >> n >> m;
    vector<vector<int>>ad_list(n+5);
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        fin >> x >> y;
        ad_list[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
        ids[i] = -1;
    for(int i = 1; i <= n; i++)
        if(ids[i] == -1)
            dfs(i, n, ad_list, low_vals, ids, on_stack, scc_stack);
    
    fout << sccs.size() << '\n';
    for(int i = 0; i < sccs.size(); i++)
        {
            for(auto j = sccs[i].begin(); j < sccs[i].end(); j++)
                fout << *j << " ";
            fout << '\n';
        }
}