Cod sursa(job #2929751)

Utilizator maria-marianita.cucos@s.unibuc.roCucos Marianita [email protected] Data 26 octombrie 2022 19:52:45
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.46 kb
#include <bits/stdc++.h>
#include <iostream>

#define MAX 100001

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

stack <int> S;
vector<int> graf[MAX],grafT[MAX],CTC[MAX];
int N, M, NrCTC;
int vizitat[MAX];

void Read()
{
    f >> N >> M;
    for(int i = 1; i <= M; i++)
    {
        int x,y;
        f >> x >> y;
        graf[x].push_back(y); // Construim graful G
        grafT[y].push_back(x); // Construim transpusa grafului G
    }
}

void DFS_graf(int Nod)
{
    vizitat[Nod] = 1;
    for(int i=0; i<graf[Nod].size();i++) {
        int Vecin = graf[Nod][i];
        if(!vizitat[Vecin])
            DFS_graf(Vecin);
    }
    S.push(Nod);
}

void DFS_graf_T(int Nod)
{
    vizitat[Nod] = 2;
    CTC[NrCTC].push_back(Nod);
    for(int i=0; i<grafT[Nod].size();i++) {
        int Vecin = grafT[Nod][i];
        if(vizitat[Vecin]==1)
            DFS_graf_T(Vecin);
    }
}

void Solve()
{
    for(int i=1;i<=N;i++)
        if(!vizitat[i])
            DFS_graf(i);
    while(!S.empty()) {
        int Nod = S.top();
        if (vizitat[Nod] == 1) {
            NrCTC++;
            DFS_graf_T(Nod);
        }
        S.pop();
    }
}
void Print()
{
    cout << NrCTC <<"\n";
    for(int i = 1; i <= NrCTC; i++) {
        for(unsigned int j = 0; j < CTC[i].size(); j++)
            cout << CTC[i][j] <<" ";
        cout<<"\n";
    }
}
int main()
{
    Read();
    Solve();
    Print();
    return 0;
}