Cod sursa(job #2868549)

Utilizator qweryclujRadu Alexandru qwerycluj Data 10 martie 2022 23:57:57
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.77 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
#include <iterator>
#include <algorithm>
#include <cstring>

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];
int niv = 0;

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

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

    for (int i : G[nod])
    {
        if (!viz[i])
        {
            dfs(i);
            nma[nod] = min(nma[nod], nma[i]);
        }
        else
        {
            if (pe_stack[i])
            {
                nma[nod] = min(nma[nod], nivel[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);
        contor++;
    }
}

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])
        {
            dfs(i);
        }
    }

    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;
}