Cod sursa(job #2928869)

Utilizator NicuDirvaDirva Nicolae NicuDirva Data 24 octombrie 2022 00:42:33
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.51 kb
#include <fstream>
#include <vector>
#include <iostream>
#include<stack>
using namespace std;

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

int n, m, nr_comp;
vector<int> l_iesiri[100005], l_intrari[100005], solutie[100005];
bool viz1[100005], viz2[100005];
stack<int> st;

//parcurgem dfs obosnuit dar adaugam pe o stiva fiecare element pe care-l vizitam
void dfs1(int nod){
    viz1[nod]=true;
    for(auto i: l_iesiri[nod]){
        if(viz1[i]==false)
            dfs1(i);
    }
    st.push(nod);
}

//parcurgem dfs al intrariilor si punem fiecare nod in componenta tare conexa corespunzatoare
void dfs2(int nod){
    solutie[nr_comp].push_back(nod);
    viz2[nod]=true;
    for(auto i: l_intrari[nod]){
        if(viz2[i]==false)
            dfs2(i);
    }
}

int main()
{
    fin>>n>>m;
    for(int i=0;i<m;i++)
    {
        int x,y;
        fin>>x>>y;
        l_iesiri[x].push_back(y);
        l_intrari[y].push_back(x);
    }

    for(int i=1;i<=n;i++)
        if(viz1[i]==false)
            dfs1(i);

//crestem numarul componentelor conexe de fiecare data cand iesim din recursie si scoatem elementul de pe stiva
    while(!st.empty()){
        if(viz2[st.top()]==false){
            nr_comp++;
            dfs2(st.top());
        }
        st.pop();
    }

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

    fin.close();
    fout.close();

    return 0;

}