Cod sursa(job #2926063)

Utilizator moise_alexandruMoise Alexandru moise_alexandru Data 16 octombrie 2022 20:00:46
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.19 kb
#include <iostream>
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
const int maxn = 100005;
vector <int> v[maxn];
stack <int> stk;
int id[maxn];
int lowlink[maxn];
bitset <maxn> pestiva;
vector <int> ctc[maxn]; /// ctc[i] = componenta tare conexa cu lowlinkul i
int n;

int currlow = 0;
int currctc = 0;
void dfs(int nod)
{
    //cerr << "Intra in nodul " << nod << "\n";
    stk.push(nod); /// pun nodul in stiva, initializez id si lowlink
    id[nod] = ++currlow;
    lowlink[nod] = currlow;
    pestiva[nod] = 1;
    //cerr << "La pasul " << nod << ":\n";
    /*for(int i = 1; i <= n; i++)
        cerr << id[i] << " ";
    cerr << "\n";
    for(int i = 1; i <= n; i++)
        cerr << lowlink[i] << " ";
    cerr << "\n\n";
    */
    for(auto it : v[nod])
    {
        if(id[it] == 0) /// vecin nevizitat
        {
            dfs(it);
            lowlink[nod] = min(lowlink[nod], lowlink[it]);
        }
        else if(pestiva[it])
            lowlink[nod] = min(lowlink[nod], lowlink[it]);
    }
    /*
    int mn = (1 << 30);
    for(auto it : v[nod]) /// iau lowlinkul minim din vecini
        mn = min(mn, lowlink[it]);
    cerr << "Minim: " << mn << "\n";
    while(id[stk.top()] != mn)
    {
        cerr << "Stiva " << stk.top() << "\n";
        lowlink[stk.top()] = mn;
        pestiva[stk.top()] = 0;
        stk.pop();
    }
    */
    if(lowlink[nod] == id[nod]) /// daca e inceput de ctc
    {
        currctc++;
        while(stk.top() != nod)
        {
            ctc[currctc].push_back(stk.top());
            pestiva[stk.top()] = 0;
            stk.pop();
        }
        ctc[currctc].push_back(nod);
        pestiva[nod] = 0;
        stk.pop();
    }
}

int main()
{
    int m;
    in >> n >> m;
    for(int i = 1; i <= m; i++)
    {
        int x, y;
        in >> x >> y;
        v[x].push_back(y);
    }
    for(int i = 1; i <= n; i++)
        if(!id[i])
            dfs(i);
    out << currctc << "\n";
    for(int i = 1; i <= currctc; i++, out << "\n")
        for(auto it : ctc[i])
            out << it << " ";
    return 0;
}