Cod sursa(job #3228866)

Utilizator bogdan_croitoru17Croitoru Constantin Bogdan bogdan_croitoru17 Data 11 mai 2024 17:33:48
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.61 kb
#include <bits/stdc++.h>
using namespace std;

class Task {
public:
    void solve() {
        read_input();
        print_output(get_result());
    }

private:
    // numarul maxim de noduri
    static constexpr int NMAX = (int)1e5 + 5; // 10^5 + 5 = 100.005

    // n = numar de noduri, m = numar de muchii/arce
    int n, m;


    // adj[node] = lista de adiacenta a nodului node
    // exemplu: daca adj[node] = {..., neigh, ...} => exista arcul (node, neigh)
    vector<int> adj[NMAX];
    vector<int>parent;
    vector<int>low_link;
    vector<int>found;
    vector<bool>in_stack;
    stack<int>nodes_stack;

    void read_input() {
        ifstream fin("ctc.in");
        fin >> n >> m;
        for (int i = 1, x, y; i <= m; i++) {
            fin >> x >> y;
            adj[x].push_back(y); // arc (x, y)
        }
        fin.close();
    }
    
    vector<vector<int>> tarjan(){
        vector<vector<int>> all_sccs;
        parent=vector<int>(n+1,-1);
        low_link=vector<int>(n+1,-1);
        found=vector<int>(n+1,-1);
        in_stack=vector<bool>(n+1,false);

        int timestamp=0;

        for(int i=1;i<=n;++i)
            if(parent[i]==-1) {
                parent[i]=i;
                dfs(i,timestamp,all_sccs);
            }

        return all_sccs;

    }

    void dfs(int node,int &timestamp,vector<vector<int>> &all_sccs){
        found[node]=++timestamp;
        low_link[node]=found[node];
        nodes_stack.push(node);
        in_stack[node]=true;

        for(auto &neight:adj[node]){
            if(parent[neight]!=-1){
                if(in_stack[neight]){
                    low_link[node]=min(low_link[node],found[neight]);
                }
                
                continue;
            }

            parent[neight]=node;
            dfs(neight,timestamp,all_sccs);
            low_link[node]=min(low_link[node],low_link[neight]);
        }

        if(found[node]==low_link[node]){
            vector<int>new_scc;
            do{
                auto x = nodes_stack.top();
                nodes_stack.pop();
                in_stack[x]=false;
                new_scc.push_back(x);
            } while(node!=new_scc.back());
            all_sccs.push_back(new_scc);
        }

    }

    vector<vector<int>> get_result() {
        //
        // TODO: Găsiți componentele tare conexe  (CTC / SCC) ale grafului orientat cu n noduri, stocat în adj.
        //
        // Rezultatul se va returna sub forma unui vector, fiecare element fiind un SCC (adică tot un vector).
        // * nodurile dintr-un SCC pot fi găsite în orice ordine
        // * SCC-urile din graf pot fi găsite în orice ordine
        //
        // Indicație: Folosiți algoritmul lui Tarjan pentru SCC.
        //

        // vector<vector<int>> all_sccs;
        // tarjan(all_sccs);
        return tarjan();
    }

    void print_output(const vector<vector<int>>& all_sccs) {
        ofstream fout("ctc.out");
        fout << all_sccs.size() << '\n';
        for (const auto& scc : all_sccs) {
            for (auto node : scc) {
                fout << node << ' ';
            }
            fout << '\n';
        }
        fout.close();
    }
};

// [ATENTIE] NU modifica functia main!
int main() {
    // * se aloca un obiect Task pe heap
    // (se presupune ca e prea mare pentru a fi alocat pe stiva)
    // * se apeleaza metoda solve()
    // (citire, rezolvare, printare)
    // * se distruge obiectul si se elibereaza memoria
    auto* task = new (nothrow) Task(); // hint: cppreference/nothrow
    if (!task) {
        cerr << "new failed: WTF are you doing? Throw your PC!\n";
        return -1;
    }
    task->solve();
    delete task;
    return 0;
}