Cod sursa(job #2928838)

Utilizator Alexandru_PotangaPotanga Alexandru Alin Alexandru_Potanga Data 23 octombrie 2022 22:44:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
void dfs(int x, vector<vector<int>> &v, stack<int> &st, vector<bool> &flag, vector<int> &id, vector<int> &low, int &curr, int &nr, vector<vector<int>> &valori)
{
    st.push(x);
    flag[x] = true;
    curr++;
    id[x] = curr;
    low[x] = curr;

    for(int i = 0; i < v[x].size(); i++)
    {
        if(id[v[x][i]] == -1)
        {
            dfs(v[x][i], v, st, flag, id , low, curr, nr, valori);
        }

        if(flag[v[x][i]] == true)
        {
            low[x] = min(low[x], low[v[x][i]]);
        }
    }

    if(id[x] == low[x])
    {
        vector<int> aux;
        int varf = -1;
        while(varf != x)
        {
            varf = st.top();
            aux.push_back(varf);
            st.pop();
            flag[varf] = false;
            low[varf] = id[x];
        }
        nr++;
        valori.push_back(aux);
    }
}

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

    int n, m, a, b;
    f >> n >> m;

    vector<vector<int>> lista_adiacenta(n+1);
    vector<bool> sflag(n+1, false);
    vector<int> lowlink(n+1, 0);
    vector<int> id(n+1, -1);
    stack<int> st;
    vector<vector<int>> valori;
    int nr = 0;

    for(int i = 0; i < m; i++)
    {
        f >> a >> b;
        lista_adiacenta[a].push_back(b);
    }
    int curr = 0;

    for(int i = 1; i < n; i++)
    {
        if(id[i] == -1)
        {
            dfs(i, lista_adiacenta, st, sflag, id, lowlink, curr, nr, valori);
        }
    }

    g << nr << "\n";

    for(int i = 0; i < valori.size(); i++)
    {
        for(int j = 0; j < valori[i].size(); j++)
        {
            g << valori[i][j] << " ";
        }
        g << "\n";
    }

    return 0;
}