Cod sursa(job #2936233)

Utilizator Calin_IftichiIftichi Albert Ioan Calin Calin_Iftichi Data 8 noiembrie 2022 13:07:13
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.04 kb
#include <bits/stdc++.h>
#define N 100001

using namespace std;

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

///complexitate n^2

int n, m;
vector <int> gr[N]; /// graful cu liste de adiacenta
vector <int> grT[N]; /// graful transpus cu liste de adiacenta


bool viz1[N]; /// pentru graful initial
bool viz2[N]; /// pentru graful transpus

stack <int> S; /// stiva pentru memorarea nodurilor in ordinea timpilor de final
vector <int> componente[N];


void Citire()
{
    fin >> n >> m; //citesc nr noduri, nr muchii
    for(int i = 1; i <= m; ++i)
    {
        int x, y;
        fin >> x >> y; //citesc muchiile
        gr[x].push_back(y); //creez lista de adiacenta pt graful initial
    }
}

void Gr_Transpus()
{
    for(int i = 1; i <= n; ++i)
        for(auto j : gr[i])
            grT[j].push_back(i); //creez graful transpus
}


void DFS(int s)
{
    viz1[s] = 1;
    for(auto i : gr[s])
        if(!viz1[i])
            DFS(i);
    S.push(s);
}

void  ParcurgereGrafInitial()
{
    for(int i = 1; i <= n; ++i)
        if(!viz1[i])
            DFS(i);
}


void DFST(int s, int ct)
{
    viz2[s] = 1;
    componente[ct].push_back(s); /// salvam nodurile pentru afisarea ulterioara
    for(auto i : grT[s])
        if(!viz2[i])
            DFST(i, ct);
}


void CTC()
{
    int ct_ctc = 0;
    while(!S.empty()) //cat timp nu e goala stiva cu parcurgerea DFS pe graful initial
    {
        int varf = S.top(); //preiau varful stivei
        S.pop(); //il elimin

        if(!viz2[varf]) //daca nu a fost vizitat in parcurgerea pe graful transpus
        {
            ct_ctc++; //cresc contor comp tare conexe
            DFST(varf, ct_ctc); //parcurg din acel varf
        }
    }

    /// afisare
    fout << ct_ctc << "\n";

    for(int i = 1; i <= ct_ctc; ++i)
    {
        for(auto j:componente[i])
                fout << j << " ";
        fout << "\n";
    }
}


int main()
{
    Citire();
    Gr_Transpus();
    ParcurgereGrafInitial();
    CTC();

    return 0;
}