Cod sursa(job #3326922)

Utilizator zionlyismAdobroaiei David zionlyism Data 1 decembrie 2025 11:52:19
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.58 kb
#include <iostream>

#include <stack>
#include <vector>
#include <algorithm>

#define NMAX 100002
using namespace std;

int n, m, nrCTC;
bool vizitat[NMAX];

vector<vector<int>> Graf;
vector<vector<int>> GrafT;

stack<int> stiva;

vector<vector<int>> compTC;

void DFS1(int nod);
void DFS2(int nod);
void sortall();
void vectorswap(int first, int second);

int main()
{
    int i, j, x, y;
    //citire si graf transpus pentru CTC
    cin>>n>>m;
    Graf.resize(n + 2); GrafT.resize(n + 2); compTC.resize(n + 2);
    for(i = 1; i <= m; i++)
    {
         cin>>x>>y;
         Graf[x].push_back(y);
         GrafT[y].push_back(x);
    }
    for(i = 1; i <= n; i++) //umplem stiva, primul DFS
        if(!vizitat[i])
           DFS1(i);
    for(i = 1; i <= n; i++) vizitat[i] = 0;
    while(stiva.size())
    {
         x = stiva.top(); stiva.pop();
         if(!vizitat[x])
            {
                nrCTC++;
                DFS2(x);
            }
    }
    cout<<nrCTC<<'\n';
    sortall();
    for(i = 0; i < compTC.size(); i++)
        if(compTC[i].size() > 0)
        {
           for(j = 0; j < compTC[i].size(); j++)
              cout<<compTC[i][j]<<' ';
           cout<<'\n';
        }
    return 0;
}

void sortall()
{
 int i;
 for(i = 0; i < compTC.size(); i++)
    sort(compTC[i].begin(), compTC[i].end());
 //bubblesort pt primul element al fiecarei comp conexe
 bool sch = 0;
 do
 {
  sch = 0;
  for(i = 1; i < compTC.size(); i++)
     if (compTC[i - 1].empty() || compTC[i].empty())
        continue;
        else
        if(compTC[i - 1][0] > compTC[i][0])
        {
            //swap la cei doi vectori
            vectorswap(i - 1, i);
            sch = 1;
        }
 }
 while(sch);
}

void vectorswap(int first, int second)
{
 int i;
 vector<int> aux;
 for(i = 0; i < compTC[first].size(); i++) aux.push_back(compTC[first][i]); //mut primul in aux
 compTC[first].resize(compTC[second].size());
 for(i = 0; i < compTC[second].size(); i++) compTC[first][i] = compTC[second][i]; //mut al doilea in primul
 compTC[second].resize(aux.size());
 for(i = 0; i < aux.size(); i++) compTC[second][i] = aux[i];  //mut aux (primul) in al doilea
}

void DFS2(int nod)
{
 vizitat[nod] = 1;
 for(int i = 0; i < GrafT[nod].size(); i++)
    if(!vizitat[GrafT[nod][i]])
    {
        DFS2(GrafT[nod][i]);
    }
 compTC[nrCTC].push_back(nod);
}

void DFS1(int nod)
{
 vizitat[nod] = 1;
 for(int i = 0; i < Graf[nod].size(); i++)
     if(!vizitat[Graf[nod][i]])
     {
        DFS1(Graf[nod][i]);
     }
 stiva.push(nod);
}