Cod sursa(job #2868234)

Utilizator qweryclujRadu Alexandru qwerycluj Data 10 martie 2022 20:04:26
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.99 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>

using namespace std;

#define MaxValue 100005

vector<int> G[MaxValue];

bool viz[MaxValue];
bool pe_stack[MaxValue];

int n, m;

int nma[MaxValue];
int nivel[MaxValue];

vector<int> sol[100000];
int contor = 0;
stack<int> st;
vector<int> vect_temp;

void dfs(int nod, int niv)
{
    //cout << "DFS nod " << nod << '\n';
    viz[nod] = true;
    nma[nod] = niv;
    nivel[nod] = niv;
    st.push(nod);
    pe_stack[nod] = true;

    for (int i : G[nod])
    {
        if (!viz[i])
        {
            dfs(i, niv + 1);
            nma[nod] = min(nma[nod], nma[i]);
        }
        else
        {
            if (pe_stack[i])
            {
                nma[nod] = min(nma[nod], nma[i]);
            }
        }
    }

    if (nma[nod] == nivel[nod])
    {
        while (st.top() != nod)
        {
            sol[contor].push_back(st.top());
            pe_stack[st.top()] = false;
            st.pop();
        }
        pe_stack[st.top()] = false;
        st.pop();
        sol[contor].push_back(nod);
        ///dam pop si la nodul curent

        if (sol[contor].size() != 1)
        {
            contor++;
        }
        else
        {
            sol[contor].clear();
        }
    }
}

int main(void)
{
    ifstream fin("ctc.in");
    ofstream fout("ctc.out");
    fin >> n >> m;
    int x, y;
    for (int i = 0; i < m; i++)
    {
        fin >> x >> y;
        G[x].push_back(y);
    }

    for (int i = 1; i <= n; i++)
    {
        if (!viz[i])
        {
            memset(pe_stack, false, sizeof(viz));
            dfs(i, 0);
        }
    }

    fout << contor << std::endl;
    for (int i = 0; i < contor; i++)
    {
        for (int j : sol[i])
        {
            fout << j << " ";
        }
        fout << std::endl;
    }

    fin.close();
    fout.close();

    return 0;
}