Cod sursa(job #2842942)

Utilizator OrzataAndreiOrzata Andrei OrzataAndrei Data 1 februarie 2022 18:55:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100010

using namespace std;

int N,M;

stack<int> Stack;
vector<int>Graf[MAX],Lowlink(MAX,-1),Indx(MAX,-1),ONstack(MAX,0);
vector<vector<int>> ANS;

void Tarjan(int x)
{
    static int index = 0;
    Indx[x] = Lowlink[x] = index;
    index++;
    Stack.push(x);
    ONstack[x] = 1;
    for (int it : Graf[x])
    {
        if (Indx[it] == -1)
            Tarjan(it);

        if (ONstack[it])
            Lowlink[x] = min(Lowlink[x], Lowlink[it]);
    }
    if (Indx[x] == Lowlink[x])
    {
        vector<int> aux;
        while (Stack.top() != x)
        {
            aux.push_back(Stack.top());
            ONstack[Stack.top()] = 0;
            Stack.pop();
        }
        aux.push_back(Stack.top());
        ONstack[Stack.top()] = 0;
        Stack.pop();
        ANS.push_back(aux);
    }
}
int main()
{
    ifstream in ("ctc.in");
    ofstream out("ctc.out");

    int x,y;
    in>>N>>M;
    for( int i = 0; i < M; ++i)
    {
        in>>x>>y;
        Graf[x].push_back(y);
    }
    for(int i = 1; i <=N; ++i)
        if (Indx[i] == -1)
            Tarjan(i);
    out << ANS.size() << "\n";
    for (auto it : ANS)
    {   for (int x : it)
            out<< x << " ";
        out << "\n";

    }
    return 0;
}