Cod sursa(job #3295782)

Utilizator tudor.brandiTudor Brandibur tudor.brandi Data 8 mai 2025 14:23:45
Problema Componente tare conexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.22 kb
#include <complex>
#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <vector>

#define INF 1e9

using namespace std;



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

int ctc;
vector<vector<int>> scc;

bool is_in_stack(int node, vector<int> &stack)
{
    for (int i = 0; i < stack.size(); ++i) {
        if (stack[i] == node)
            return true;
    }
    return false;
}

void DFS(int node,int &timestamp, vector<vector<int>> &adj, vector<int> &parent,
         vector<int> &viz, vector<int> &low_link, vector<int> &stack)
{
    viz[node] =  ++timestamp;
    low_link[node] = viz[node];
    stack.push_back(node);

    for (int neigh : adj[node]) {

        if (parent[neigh] > 0) {

            if (is_in_stack(neigh, stack))
                low_link[node] = min(low_link[node], viz[neigh]);
        
            continue;
        }
        parent[neigh] = node;

        DFS(neigh, timestamp, adj, parent, viz, low_link, stack);

        low_link[node] = min (low_link[node], low_link[neigh]);

    }

    if (low_link[node] == viz[node]) {

        vector<int> comp;
        int x;
        do {
            cout << " printez\n";
            x = stack.back();
            stack.pop_back();
            comp.push_back(x);
        } while (x != node);

        ctc++;
        scc.push_back(comp);
    }

}

void tarzan(int N, vector<vector<int>> &adj)
{
    vector<int> parent (N + 1, -1);
    vector<int> viz (N + 1, INF);
    vector<int>low_link(N + 1, INF);

    vector<int> stack;

    int timestamp = 0;

    for (int i = 1; i <= N; ++i) 
    {
        if (parent[i] < 0) {
            cout << i << '\n';
            parent[i] = i;
            cout<< "apelez dfs\n";
            DFS(i, timestamp, adj, parent, viz, low_link, stack);
            cout << "ise din dfs\n";
        }
    }

}

int main()
{

    int N, M;
    fin >> N >> M;
    vector<vector<int>> adj(N + 1, vector<int>());
    for (int i = 0; i < M; ++i) {
        int x, y;
        fin >> x >> y;
        adj[x].push_back(y);
    }

    tarzan(N, adj);
    cout<<"ies din tarzazn\n";

    fout << ctc << '\n';

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

    return 0;
}