Cod sursa(job #2798159)

Utilizator Andreea__Zavoiu Andreea Andreea__ Data 10 noiembrie 2021 23:11:34
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.06 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define Nmax 100001
using namespace std;

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

// aici folosesc 2 vectori de noduri vizitate, unul pt graful normal, unul pt graful transpus (in ideea alg. plus minus)
int n, m, nrCTC, visited1[Nmax], visited2[Nmax], comp[Nmax];
vector<int> la[Nmax], grafTranspus[Nmax], sol[Nmax], S; // folosim graful transpus doarece ne intereseaza sa putem ajunge din orice nod
                                            // al componentei conexe in oricare altul tot al sau => verificam asa accesibilitatea
//stack<int> S;   // pe baza ideii de la DFS

void dfsG(int x)
{
    visited1[x] = 1;

    for (int i = 0; i < la[x].size(); ++i)
        if (!visited1[la[x][i]]) {  // marcam in viz1 nodurile vizitate de dfs aplicat pe graful normal (in semn de plus)
            //cout << "->dfsG(" << la[x][i] << ")\n";
            dfsG(la[x][i]);
            //cout << "Back to " << x << endl;
        }

    //cout << "Push " << x << endl;
    S.push_back(x); // ca sa pastreze ordinea de finalizare a nodurilor => parcurg GT in ordinea in care le scot de pe stiva
}

void dfsGT(int x)   // aplicam dfs si pe graful transpus
{
    comp[x]=nrCTC; // ii atribui nodului componenta TC curenta
    // cout << "sol[" << nrCTC << "].push_back( " << x << ");\n";
    sol[nrCTC].push_back(x);
    visited2[x] = 1;

    for (int i = 0; i < grafTranspus[x].size(); ++i)
        if (!visited2[grafTranspus[x][i]])   // daca sunt marcate inseamna ca nu fac parte din aceasta CTC sau le-am viz deja pt CTC curenta
        {
            // cout << "->dfsGT(" << grafTranspus[x][i] << ")\n";
            dfsGT(grafTranspus[x][i]);
            // cout << "Back to " << x << endl;
        }
}


void Kosaraju()
{
    for (int i=1; i<=n; i++)
        if (!visited1[i]) {
            //cout << "->dfsG(" << i << ")\n";
            dfsG(i);
        }


//    for (int i=1; i<=n; i++) {
//        visited[i] = false; // clear-ul vectorului pt a-l refolosi la urm dfs
//    }

    // cout << "Stiva in ordinea inversa intrarii:\n";
    for (int i = S.size()-1; i>=0; i--) {
        if (!visited2[S[i]]) {
            dfsGT(S[i]);
            nrCTC++;
        }
    }
//    while (!S.empty())
//    {
//        int v = S.top();
//        cout << v << " ";
//        S.pop();
//        if (!visited2[v]) {
//            // cout << "->dfsGT(" << v << ")\n";
//            dfsGT(v);
//            // cout << "Back to " << v << " where nrCTC = ";
//            nrCTC++;
//            // cout << nrCTC << endl;
//        }
//    }
}


int main() {

    int x, y;
    fin >> n >> m;
    for (int i=0; i<m; i++) { // obs: in la[x], nodurile adiacente cu x nu se pun in ordine crescatoare, ci in ordinea citirii
        fin >> x >> y;
        la[x].push_back(y); // graf orientat
        grafTranspus[y].push_back(x);
    }

    Kosaraju();
    fout << nrCTC << endl;

    for(int i = 0; i < nrCTC; ++i) {
        for(int j = 0; j < sol[i].size(); ++j)
            fout << sol[i][j] << " ";
        if (i!=nrCTC-1)
            fout << endl;
    }

    return 0;
}