Cod sursa(job #2797613)

Utilizator andreea.ioanaSora Andreea-Ioana andreea.ioana Data 10 noiembrie 2021 12:06:01
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.18 kb
#include <iostream>
#include <fstream>
#include <queue>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("ctc.in");
ofstream fout("ctc.out");
int n;
void dfs1(int nod, vector <int> &vizitat, stack <int> &stiva, vector <vector<int>> listaAd)
{
    vizitat[nod] = 1;
    for (int i = 0; i < listaAd[nod].size(); i++)
    {
        int nod_curent = listaAd[nod][i];
        if (vizitat[nod_curent] == 0)
            dfs1(nod_curent, vizitat, stiva, listaAd);
    }
   stiva.push(nod);
}

void dfs2(int nod, vector <int> &vizitat, vector <vector<int>> listaTr, vector <vector<int>> &rez, vector<int> &vector_aux)
{
    //cout << nod << " ";
   // rez[nr].push_back(nod);
    vector_aux.push_back(nod);
    vizitat[nod] = 1;
    for (int i = 0; i < listaTr[nod].size(); i++)
    {
        int nod_curent = listaTr[nod][i];
        if (vizitat[nod_curent] == 0)
            dfs2(nod_curent, vizitat, listaTr, rez, vector_aux);
    }
}

void ctc(vector <vector<int>> listaTr, vector <vector<int>> listaAd)
{
    int nr = 0;
    vector <int> vizitat(n + 1, 0);
   // vector <int> vizitatTr(nrN + 1, 0);
    stack <int> stiva;
    vector <vector<int>> rez(n + 1);
    for (int i = 1; i <= n; i++)
        if (vizitat[i] == 0)
            dfs1(i, vizitat, stiva, listaAd);
    for (int i = 1; i <= n;i++)
        vizitat[i] = 0;
    while (stiva.empty() == 0)
    {
       int v = stiva.top();
       stiva.pop();
       if (vizitat[v] == 0)
       {
          vector <int> vector_aux;
          dfs2(v, vizitat, listaTr, rez, vector_aux);
          rez.push_back(vector_aux);
          nr++;
       }
    }
    fout << nr;
    for (int i = 0; i < rez.size(); i++)
    {
       for (int j = 0; j < rez[i].size(); j++)
           fout << rez[i][j] << " ";
       fout << "\n";
    }
}

int main()
{
    int m, st, dr;
    fin >> n >> m;
    vector <vector<int>> listaAd (n + 1);
    vector <vector<int>> listaTr (n + 1);
    for (int i = 1; i <= m; i++)
    {
        fin >> st >> dr;
        listaAd[st].push_back(dr);
        listaTr[dr].push_back(st);
    }
    ctc(listaTr, listaAd);
    fin.close();
    fout.close();
    return 0;
}