Cod sursa(job #2928771)

Utilizator Diana_14Diana Muscalu Diana_14 Data 23 octombrie 2022 20:33:09
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.39 kb
#include <iostream>
#include <vector>
#include <fstream>
#include <stack>

using namespace std;

int n, nr_ctc;
///construim un vector de vectori in care retinem nodurile pe care le contine fiecare componenta conexa
vector <vector <int>> sol;

vector <vector <int>> adj; ///lista adiacenta
vector <vector <int>> adj_t; ///lista adiacenta transpusa

vector <int> viz;
stack <int> st;

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

void afisare()
{
    ///afisam nr ctc
    g<<nr_ctc<<"\n";

   ///aici afisam nodurile fiecarei ctc
    for(int i=1; i <= nr_ctc ; i++)
    {
        for(auto v: sol[i])
        {
            g<< v <<" ";
        }
        g<<"\n";
    }
}

void dfs(int nod)
{
    for(auto i=0; i < adj[nod].size();i++)
    {
        if(viz[adj[nod][i]]==0)
        {
            viz[adj[nod][i]]=1;
            dfs(adj[nod][i]);
        }
    }
    /// introducem nodurile vizitate in dfs intr-o stiva pentru a putea aplica apoi dfs-ul transpus
    st.push(nod);
}
void dfs_t(int nod)
{
    ///daca nodul e vizitat in ambele parcurgeri dfs, marcam in viz cu 2
    viz[nod] = 2;

    ///adaugam nodul in solutie
    sol[nr_ctc].push_back(nod);

    ///parcurgem nodurile vecine si daca au fost vizitate apelam df-ul trasnpus
    for( auto i = 0 ;i < adj_t[nod].size(); i++)
    {
        if(viz[adj_t[nod][i]] == 1)
        {
            dfs_t(adj_t[nod][i]);
        }
    }
}

void face(int m)
{
    for(int i=1; i <= m ; i++)
    {   int a,b;
        f>>a>>b;
        adj[a].push_back(b);
        adj_t[b].push_back(a);
    }

}
int main()
{
    int n, m;
    f>>n>>m;

    sol.resize(n+1);
    viz.resize(n+1,0);
    adj.resize(n+1);
    adj_t.resize(n+1);

    face(m);

    ///marcam daca nodurile au fost vizitate sau nu atat in rpima cat si in a doua parcurgere
    for(int i = 1; i <= n ; i++)
    {   ///daca nodul nu a fost vizitat, atunci il marcam ca vizitat si apoi apelam functia dfs
        if(viz[i] == 0)
        {
            viz[i]=1;
            dfs(i);
        }
    }

    ///cat timp avem elemente in stiva, verificam daca nodul a fost vizitat in dfs, iar apoi apelam dfs-ul transpus
    while(st.size() > 0)
    {
        int nod = st.top();
        st.pop();
        if(viz[nod]==1)
        {
            nr_ctc++;
            dfs_t(nod);

        }
    }

    afisare();

    return 0;
}