Cod sursa(job #3198163)

Utilizator alexandrubilaBila Alexandru-Mihai alexandrubila Data 28 ianuarie 2024 14:12:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.67 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int NMAX = 100000;

int N, M, nrc;
vector <int> G[NMAX + 1], CTC[NMAX + 1];
int D[NMAX + 1], Dmin[NMAX + 1], Timp = 0;

stack<int>S;
bool inSt[NMAX + 1];

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


void citire()
{
    int x, y;
    f >> N >> M;

    for (int i = 1; i <= M ; i++)
    {
        f >> x >> y;
        G[x].push_back(y);
    }

}

void DFS(int x)
{
        D[x] = ++Timp;
        Dmin[x] = D[x];
        S.push(x);
        inSt[x] = 1;
        for (auto &y : G[x])
        {
            if (D[y] == 0) ///muchie de arbore
            {
                DFS(y);
                Dmin[x] = min(Dmin[x], Dmin[y]);
            }
            else
            {
                if (inSt[y] == 1) ///muchie de intoarcere
                    Dmin[x] = min(Dmin[x], Dmin[y]);
                ///altfel este o muchie inainte sau o muchie cross cate alta cc si nu ne int

            }

        }
        //
        ///daca x nu poate urca mai sus de x, inseamna ca x este radacina a ctc
        if (Dmin[x] == D[x]) ///x = rad ctc
        {
            int u;
            nrc++;
            do ///scoatem nodurile ctc de pe stiva
            {
                u = S.top();
                CTC[nrc].push_back(u);
                S.pop();
                inSt[u] = 0;
            } while (x != u);
            
        }
}

void afisare()
{
    g << nrc << '\n';
    for (int i = 1 ; i <= nrc; i++)
    {
        for (auto &x : CTC[i])
            g << x << ' ';
        g << '\n';
    }
}

int main()
{
    citire();
    for (int i = 1; i <= N ; i++)
        if (D[i] == 0)
            DFS(i);
    afisare();

    return 0;
}