Cod sursa(job #3341517)

Utilizator ZsomborZsombor Horvay Zsombor Data 19 februarie 2026 19:59:26
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.81 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

ifstream be("ctc.in");
ofstream ki("ctc.out");

struct vertices
{
    int index, lowlink;
    bool onstack;

    vertices()
    {
        index = -1;
        lowlink = 0;
        onstack = false;
    }
};

void tarjan(int v, int &index, stack<int> &s, vector<vertices> &V, vector<vector<int>> &E, vector<vector<int>> &ans)
{
    V[v].index = index;
    V[v].lowlink = index;
    
    index++;

    s.push(v);
    V[v].onstack = true;

    for(int w : E[v])
    {
        if(V[w].index == -1)
        {
            tarjan(w, index, s, V, E, ans);
            V[v].lowlink = min(V[v].lowlink, V[w].lowlink);
        }else if(V[w].onstack)
        {
            V[v].lowlink = min(V[v].lowlink, V[w].index);
        }
    }

    if(V[v].lowlink == V[v].index)
    {
        vector<int> component;
        int w;

        do
        {
            w = s.top();

            s.pop();
            V[w].onstack = false;

            component.push_back(w);
        }while(v != w);

        ans.push_back(component);
    }
}

int main()
{
    int n, m;
    be >> n >> m;

    vector<vector<int>> E(n + 1);

    for(int i = 0; i < m; i++)
    {
        int u, v;
        be >> u >> v;

        E[u].push_back(v);
    }

    vector<vertices> V(n + 1);
    stack<int> s;

    vector<vector<int>> ans;
    
    int index = 0;

    for(int i = 1; i <= n; i++)
    {
        if(V[i].index == -1)
        {
            tarjan(i, index, s, V, E, ans);
        }
    }

    int size = (int)ans.size();

    ki << size << "\n";

    for(int i = 0; i < size; i++)
    {
        for(int j : ans[i])
        {
            ki << j << " ";
        }

        ki << "\n";
    }

    return 0;
}