Cod sursa(job #2664565)

Utilizator paulaiugaPaula Iuga paulaiuga Data 28 octombrie 2020 20:20:53
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.29 kb
#include <iostream>
#include <fstream>
#include <bits/stdc++.h>

using namespace std;
ifstream in("ctc.in");
ofstream out("ctc.out");
//similar cu minimizarea dfa de la LFA
//Algoritmul lui Kosaraju
vector<int> adiacenta[100009];
vector<int> transpusa[100009];///se inverseaza sensul arcelor =>o parcurgere DFS determina o componenta conexa
vector<int> componente_conexe[100009];///pe pozitia 1 vom aveam lista cu nodurile primei componenete conexte ... pe pozitia nr_comp vom avea ultima componenta conexa
int vizitat [100009];///initializat cu zero
stack<int> stiva;


int nr_comp;

void DFS(int nod)
{
   vizitat[nod] = 1;
    for(size_t i=0; i<adiacenta[nod].size(); i++) {
        if(!vizitat[adiacenta[nod][i]])
            DFS(adiacenta[nod][i]);
    }
                         ///ca la sortarea topologica se salveaza nodul dupa ce ne-am intors din parcurgerea recursiva in stiva
    stiva.push(nod);

}


void DFS2(int nod)
{
   vizitat[nod] = 2;///il vizitam a doua oara in gradul transpus
   componente_conexe[nr_comp].push_back(nod);///il inseram in componenta conexa din care face parte

    for(size_t i=0; i<transpusa[nod].size();i++) {
        if(vizitat[transpusa[nod][i]] == 1)
            DFS2(transpusa[nod][i]);
    }


}

int main()
{
    int N,M,x,y;
    in>>N>>M;
     for(int i =1; i <=M ;i++)
    {
        in>>x>>y;
        adiacenta[x].push_back(y);//graf orientat x y  muchie => doar x e vecinul lui y
        transpusa[y].push_back(x);//construim tanspusa grafului dat;

    }



    for(int i = 1; i <= N; i++)
    {
        if(!vizitat[i])
            DFS(i);
    }

    //stiva.erase( unique( arr.begin(), arr.end() ), arr.end() );

    while(!stiva.empty())//scoatem nodurile din stiva;
    {
        int nod = stiva.top();
        if(vizitat[nod] == 1)///daca elem din stiva nu a fost vizitat si in parcurgerea transpusei
        {
            nr_comp ++;///inseamna ca apartine unei alte componente conexe
            DFS2(nod);
        }

        stiva.pop();
    }


    out<<nr_comp<<"\n";

    //out<<"----";

    for(int i = 1; i <= nr_comp; i++)
    {
        for(size_t j = 0; j < componente_conexe[i].size(); j++)
            out<<componente_conexe[i][j]<<" ";

        out<<"\n";
    }

    return 0;
}