Cod sursa(job #2925806)

Utilizator alex2209alexPavel Alexandru alex2209alex Data 16 octombrie 2022 09:43:15
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
/*
Algoritmul lui Tarjan
Din fiecare nod nevizitat inca se face un dfs
-marcam index de nod(id-ul) si lowLink(cel mai mic id la care se pate ajunge prin subarborele nodului) ca fiind nextIndex
-nextIndex creste
-punem nodul pe coada
-pentru toti vecinii lui nod daca unul nu e vizitat atunci se face dfs din nodul respectiv si dupa lowLink[nodul curent] e
minimul dintre valuarea sa si lowLink[vecin]
-altfel daca vecinul nu e pe coada muchia e intre doua componente conexe diferite
-altfel lowLink de nod e min(lowLink[nod], index[vecin])

Daca dupa ce se trec prin toti vecinii lowLink[nod] = index[nod] nod e radacina unui ctc si se elimina de pe stack toate nodurile care apartin acetui ctc

Alfel nu e radacina unui ctc si trebuie sa ramana pe stack

Complexitate O(N + M)
*/
#include <bits/stdc++.h>

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

vector<int> edges[100001], cTC[100001];
stack<int> st;

class Solution {
    int n, nextIndex = 1, index[100001], lowLink[100001], numberCTC;
    bool onStack[100001];
public:
    void run() {
        read();
        solve();
        scrie();
    }
    void read() {
        int m;
        f >> n >> m;
        while(m--) {
            int x, y;
            f >> x >> y;
            edges[x].push_back(y);
        }
        f.close();
    }
    void solve() {
        for(int i = 1; i <= n; ++i) {
            if(!index[i]) {
                dfs(i);
            }
        }
    }
    void dfs(int node) {
        index[node] = nextIndex;
        lowLink[node] = nextIndex;
        nextIndex++;
        onStack[node] = true;
        st.push(node);
        for(auto it : edges[node]) {
            if(index[it] == 0) {
                dfs(it);
                lowLink[node] = min(lowLink[node], lowLink[it]);
            } else if(onStack[it]) {
                lowLink[node] = min(lowLink[node], index[it]);
            }
        }
        if(index[node] == lowLink[node]) {
            numberCTC++;
            int x;
            do {
                x = st.top();
                cTC[numberCTC].push_back(x);
                st.pop();
                lowLink[x] = index[node];
                onStack[x] = false;
            } while(x != node);
        }
    }
    scrie() {
        g << numberCTC << '\n';
        for(int i = 1; i <= numberCTC; ++i) {
            for(auto it : cTC[i]) {
                g << it << " ";
            }
            g << '\n';
        }
        g.close();
    }
};

int main()
{
    Solution solution;
    solution.run();
    return 0;
}