Cod sursa(job #2715154)

Utilizator dimi999Dimitriu Andrei dimi999 Data 3 martie 2021 09:00:43
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.47 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

vector <int> v[100005];

int lvl[100005], in_st[100005], k, llink[100005];

stack <int> st;

vector < vector <int> > ans;

void tarjan(int node)
{
    lvl[node] = llink[node] = ++k;
    in_st[node] = true;
    st.push(node);

    for(int i = 0; i < (int)v[node].size(); i++)
        if(lvl[v[node][i]] == 0)
    {
        tarjan(v[node][i]);

        llink[node] = min(llink[node], llink[v[node][i]]);
    }
    else
        if(in_st[v[node][i]] == true)
            llink[node] = min(llink[node], llink[v[node][i]]);

    if(lvl[node] == llink[node])
    {
        vector <int> aux;

        int naux = 0;

        do
        {
            naux = st.top();
            aux.push_back(naux);
            st.pop();
            in_st[naux] = false;
        }
        while(naux  != node);

        ans.push_back(aux);
    }

}

int main()
{
    int N, M;

    fin >> N >> M;

    for(int i = 1; i <= M; i++)
    {
        int x, y;

        fin >> x >> y;

        v[x].push_back(y);

    }

    for(int i = 1; i <= N; i++)
        if(lvl[i] == 0)
        tarjan(i);

    fout << (int)ans.size() << '\n';

    for(int i = 0; i < (int)ans.size(); i++)
    {
        for(int it = 0; it < (int)ans[i].size(); it++)
            fout << ans[i][it] << " ";
        fout << '\n';
    }

    return 0;

}