Cod sursa(job #2928770)

Utilizator TeoDiDiaconescu Teodora TeoDi Data 23 octombrie 2022 20:31:01
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.03 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("ctc.in");
ofstream fout("ctc.out");

int n;

class Solve {
    vector<vector<int> > sol;
    vector<vector<int> > lista;
    int nr;
    vector<int> f;
    vector<int> s;
    vector<int> low;
    vector<int> id;
    int top;
    int idact;

    void Dfs(int act){
        s[++top] = act;
        f[act] = 1;
        id[act] = low[act] = ++idact;
        for(auto next:lista[act])
        {
            if(id[next] == -1) Dfs(next);
            if(f[next] == 1) {
                if(low[act] > low[next]) low[act] = low[next];
            }
        }
        if(id[act] == low[act])
        {
            vector<int> aux;
            aux.push_back(act);
            for(int j = top;;j--)
            {
                if(s[top] == act) {top--; break;}
                aux.push_back(s[j]);
                top--;
                f[s[j]] = 2;
                id[s[j]] = id[act];
            }
            sol.push_back(aux);
        }
    };

public:
    vector<vector<int> > Tarjan(int nr, vector<vector<int> > &lista) {
        this->lista = lista;
        this->nr = nr;
        for(int i = 0; i <= n; i++)
        {
            f.push_back(-1);
            s.push_back(0);
            id.push_back(-1);
            low.push_back(100000);
        }
        top = -1;
        idact = 0;
        sol.clear();
        for(int i = 1; i <= nr; i++)
        {
            if(f[i] == -1) Dfs(i);
        }
        /*for(auto x:sol)
        {
            for(auto y: x)
                cout<<y<<' ';
            cout<<'\n';
        }*/
        return sol;
    }


};

vector<vector<int> > Citire()
{
    int m, x, y;
    fin>>n>>m;
    vector<vector<int> > lista(n+1);
    for(int i = 0; i < m; i++)
    {
        fin>>x>>y;
        lista[x].push_back(y);
    }
    return lista;
}

int main() {
    vector<vector<int> > v;
    Solve a;
    v = Citire();
    v = a.Tarjan(n, v);
    fout<<v.size()<<'\n';
    for(auto x:v)
    {
        for(auto y: x)
            fout<<y<<' ';
        fout<<'\n';
    }
    return 0;
}