Cod sursa(job #2926494)

Utilizator gizzehhhAsavoaei Bianca Gabriela gizzehhh Data 17 octombrie 2022 21:00:47
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <iostream>
#include <bits/stdc++.h>
#define N 100005
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");

/// Vom folosi algoritmul lui Tarjan

vector < vector <int> > la(N), sol(N); /// matricea de adiacenta si lista de solutii
vector <int> lowLink(N), disc(N), stkItem(N); /// lowLink[i] = x --> x e cel mai mic nod la care ajunge nodul i prin DFS
stack <int> stk; /// adaugam nodurile valide pe masura ce parcugem cu DFS, nodurile sunt eliminate de fiecare data cand s a gasit
                 /// o SCC
int n, m, x, y, i, j, cnt, g;


void Citire(){

    fin >> n >> m;
    for(i=1; i<=m; i++)
    {
        fin >> x >> y;
        la[x].push_back(y);
    }
}

void findComponent(int node) {
    stk.push(node);
    stkItem[node] = 1;
    disc[node] = lowLink[node] = ++g;

    ///parcurgem fiecare lista
    for (int i = 0; i < la[node].size(); i++) {
        int x = la[node][i];

        ///inseamna ca trebuie sa ii gasim componenta
        if (disc[x] == -1) {
            findComponent(x);
        }

        /// actualizam cel mai mic nod la care poate ajunge node cu un alt posibil candidat, valoarea
        /// pe care deja o are sau valoarea pe care o afla nodul incident
        if( stkItem[x] != 0 ) {
            lowLink[node] = min(lowLink[node], lowLink[x]);
        }
    }

    /// daca, componenta actuala a fost "inchisa", le dam pop din stiva pana ajungem inapoi la nodul de unde am plecat
    /// facem stkItem = 0 ca sa le punem in solutia finala
    int poppedItem = 0;
    if (disc[node] == lowLink[node]) {
        while (stk.top() != node) {
            poppedItem = stk.top();
            stkItem[poppedItem] = 0;
            lowLink[poppedItem] = disc[node];
            stk.pop();
        }

        poppedItem = stk.top();
        stkItem[poppedItem] = 0;
        lowLink[poppedItem] = disc[node];
        stk.pop();

        cnt++;
    }
}

void WriteSol(){

    for(int i = 1; i <= n; i++)
        sol[ lowLink[i] ].push_back(i);

    fout << cnt << '\n';

    for(int i = 1; i <= n; i++) {
        if( sol[i].size() ) {
            for(int j = 0; j < sol[i].size(); j++) {
                fout << sol[i][j] << " ";
            }
            fout << '\n';
        }
    }
}
int main()
{
    Citire();

    for(i=1; i<=n; i++)
        disc[i] = lowLink[i] = -1;

    for(i=1; i<=n; i++)
        if(disc[i] == -1)
              findComponent(i);

    WriteSol();
    return 0;
}