Cod sursa(job #2785525)

Utilizator smoc_georgemarianSmoc George-Marian smoc_georgemarian Data 18 octombrie 2021 20:41:30
Problema Componente tare conexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.79 kb
#include <bits/stdc++.h>
#define NMAX 100009
#define IN_FILE "ctc.in"
#define OUT_FILE "ctc.out"
using namespace std;

stack<int> S;
vector<int> g[NMAX];
vector<int> components[NMAX];
int no_components;
int index_value;
int ind[NMAX], lnk[NMAX];
bool on_stack[NMAX];
void tarjan(int k);
int main()
{
    int n, m;
    FILE *fd_in = fopen(IN_FILE, "r");
    FILE *fd_out = fopen(OUT_FILE, "w");

    fscanf(fd_in, "%d %d", &n, &m);
    for (int i = 0; i < m; i++)
    {
        int x, y;
        fscanf(fd_in, "%d %d", &x, &y);
        g[x].push_back(y);
    }
    for (int i = 1; i <= n; i++)
    {
        if (!ind[i])
            tarjan(i);
    }
    fprintf(fd_out, "%d\n", no_components);
    for (int i = 0; i < no_components; i++)
    {
        for (auto component_element : components[i])
        {
            fprintf(fd_out, "%d ", component_element);
        }
        fprintf(fd_out, "\n");
    }

    return 0;
}
void tarjan(int node_index_value)
{
    index_value++;
    ind[node_index_value] = index_value;
    lnk[node_index_value] = index_value;
    S.push(node_index_value);
    on_stack[node_index_value] = true;
    for (auto ngb_index_value : g[node_index_value])
    {
        if (!ind[ngb_index_value])
        {
            tarjan(ngb_index_value);
            lnk[node_index_value] = min(lnk[node_index_value], lnk[ngb_index_value]);
        }
        else if (on_stack[ngb_index_value])
        {
            lnk[node_index_value] = min(lnk[node_index_value], ind[ngb_index_value]);
        }
    }

    if (lnk[node_index_value] == ind[node_index_value])
    {
        int stack_elem;
        do
        {
            stack_elem = S.top();
            S.pop();
            components[no_components].push_back(stack_elem);
        } while (stack_elem != node_index_value);
        no_components++;
    }
}