Cod sursa(job #2794668)

Utilizator CaptnBananaPetcu Tudor CaptnBanana Data 5 noiembrie 2021 11:42:32
Problema Componente tare conexe Scor 40
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.31 kb
#include <bits/stdc++.h>

using namespace std;

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

const int N = 1e5 + 1;
int n, m, x, y, cnt, indecs;
vector<int> c[N], comp[N];
stack<int> s;
struct varf{
    int ind = -1, lowlink;
    bool peStiva = 0;
}v[N];

void tarzan(int nod){
    v[nod].ind = v[nod].lowlink = indecs;
    s.push(nod);
    v[nod].peStiva = 1;
    indecs++;
    for(int y: c[nod]){
        if(v[y].ind == -1){
            tarzan(y);
            v[nod].lowlink = min(v[nod].lowlink, v[y].lowlink);
        }else if(v[y].peStiva)
            v[nod].lowlink = min(v[nod].lowlink, v[y].ind); // teoretic asa e corect, dar merge si v[y].lowlink
    }

    if(v[nod].ind == v[nod].lowlink){
        cnt++;
        int w;
        do{
            w = s.top();
            comp[cnt].push_back(w);
            v[w].peStiva = 0;
            s.pop();
        }while(w != nod);
    }
}

int main(){
    f >> n >> m;
    for(int i = 0; i < m; i++){
        f >> x >> y;
        c[x].push_back(y);
    }

    f.close();
    for(int i = 1; i <= n; i++){
        if(v[i].ind == -1)
            tarzan(i);
    }

    g << cnt << '\n';
    for(int i = 1; i <= cnt; i++){
        for(int nod: comp[i])
            cout << nod << ' ';

        g << '\n';
    }

    g.close();
}