Cod sursa(job #2907428)

Utilizator maria.ianiIani Maria maria.iani Data 30 mai 2022 10:23:00
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <cstring>
#include <stack>
#include <algorithm>

using namespace std;
ifstream f("ctc.in");
ofstream g("ctc.out");

#define MAX 100001

int N,M,x,y,i,idx=1;
vector <int> A[MAX], aux;
int viz[MAX], lowlink[MAX], in_stack[MAX];
stack<int> current_component;
vector<vector <int>> components;

void citire()
{
    f >> N >> M;
    for (i = 1; i <= M; i++)
    {
        f >> x >> y;
        A[x].push_back(y);
    }
    f.close();
}

void tarjan(int nod)
{
    viz[nod] = lowlink[nod] = idx++;
    current_component.push(nod);
    in_stack[nod] = 1;

    for (int j: A[nod]) {
        if (!viz[j]) {
            tarjan(j);
            lowlink[nod] = min(lowlink[nod], lowlink[j]);
        }
        else if (in_stack[j])
            lowlink[nod]= min(lowlink[nod], viz[j]);
    }

    if (viz[nod] == lowlink[nod]) {
        aux.clear();
        int node;
        do {
            node = current_component.top();
            current_component.pop();
            aux.push_back(node);
            in_stack[node] = 0;
        } while (node != nod);
        components.push_back(aux);
    }
}

int main()
{
    // folosesc liste de vecini pentru retinerea grafului
    citire();
    // marchez toate nodurile ca fiind nevizitate
    memset(viz, 0, sizeof(viz));
    memset(in_stack, 0, sizeof(in_stack));
    for (i=1; i<=N; i++)
        if (!viz[i]) {
            tarjan(i);
        }

    g<<components.size()<<endl;

    reverse(components.begin(), components.end());
    for (i=0; i<components.size(); i++) {
        reverse(components[i].begin(), components[i].end());
        for (auto j: components[i])
            g<<j<<" ";
        g<<endl;
    }

    g.close();
    return 0;
}