Cod sursa(job #2797524)

Utilizator rimihaiMihai Radu-Ioan rimihai Data 10 noiembrie 2021 02:46:21
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.49 kb
#include<bits/stdc++.h>

using namespace std;

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

vector<int> lista_adiacenta[100001], lista_adiacenta2[100001], componente[100001], stiva;
unordered_map<int,bool> vector_vizitat,vector_vizitat_2;

int n,m,x,y,nr_componente_tari_conexe;

void DFS1(int x)
{
    vector_vizitat[x] = true;

    for (int i=0; i <lista_adiacenta[x].size(); ++i)
        if (vector_vizitat[lista_adiacenta[x][i]]==0)
               DFS1(lista_adiacenta[x][i]);

     stiva.push_back(x);
}

void DFS2(int x)
{
    vector_vizitat_2[x] = true;

    componente[nr_componente_tari_conexe].push_back(x);

    for (int i = 0; i < lista_adiacenta2[x].size(); ++i)
        if (vector_vizitat_2[lista_adiacenta2[x][i]]==0)
               DFS2(lista_adiacenta2[x][i]);

}


int main()
{
    fin>>n>>m;
    for(int i=0; i<m; i++)
    {
        fin>>x>>y;
        lista_adiacenta[x].push_back(y);
        lista_adiacenta2[y].push_back(x);
    }
    for(int i=1; i<=n; i++)
        if(!vector_vizitat[i])
            DFS1(i);

   for(int i=stiva.size()-1;i>=0 ;i--)
    {
       if(!vector_vizitat_2[stiva[i]])
      {
          DFS2(stiva[i]);
          nr_componente_tari_conexe++;
      }
    }

    fout<<nr_componente_tari_conexe<<'\n';
    for(int i=0 ;i <nr_componente_tari_conexe ; i++)
    {
        for(int j = 0; j <componente[i].size(); j++)
            fout<<componente[i][j]<<" ";

        fout<<'\n';
    }

    return 0;

}