Cod sursa(job #2736955)

Utilizator dimi999Dimitriu Andrei dimi999 Data 4 aprilie 2021 11:18:41
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.4 kb
#include <bits/stdc++.h>
using namespace std;

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

int N, M;

int idx[100005], llink[100005], k;
stack <int> st;
bool inst[100005];

vector <int> v[100005];

vector <vector <int>> ans;

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

    for(int i = 0; i < v[node].size(); i++)
        if(idx[v[node][i]] == 0)
    {
        tarjan(v[node][i]);
        llink[node] = min(llink[node], llink[v[node][i]]);
    }
    else
        if(inst[v[node][i]] == true)
            llink[node] = min(llink[node], llink[v[node][i]]);

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

        int naux;

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

        ans.push_back(aux);
    }
}

int main()
{
    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(idx[i] == 0)
            tarjan(i);

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

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

    return 0;
}