Cod sursa(job #3270186)

Utilizator andriescucosminaandriescu cosmina andriescucosmina Data 22 ianuarie 2025 12:48:51
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.73 kb
#include <iostream>
#include <vector>
#include <fstream>
#define NMAX 100001

using namespace std;

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

int n, nr, nrc;

//graful initial prin liste de adiacenta
 vector<int> G[NMAX];

//graful transpus
 vector<int> GT[NMAX];

 int post[NMAX];
 bool viz[NMAX];

 vector<int> ctc[NMAX]; //contine vf din comp tare conexa i

 void DFS(int x);
 void DFST(int x);

 void citire();
 void afisare();

 void citire()
 {
    int m, i, x, y;
    fin >> n >> m;
    for(int i=0; i<m; i++)
    {
        fin >> x >> y;
        //exista arc de la x la y in G
        G[x].push_back(y);
        //exista arc de la y la x in GT
        GT[y].push_back(x);
    }
 }

 void afisare()
 {
     fout << nrc << " " << endl;
     for(int i=1; i<=nrc; i++)
     //afisaz vf din comp tacre conexa i
     {
         for(int j=0; j<ctc[i].size(); j++)
            fout << ctc[i][j] << " ";
            fout << endl;
     }
        fout << endl;
 }

 void DFS(int x)
 {
     int i;
     viz[x]=1;
     for(i=0; i<G[x].size(); i++)
        if(!viz[G[x][i]])
            DFS(G[x][i]);
    post[++nr]=x;
 }

  void DFST(int x)
 {
     int i;
     viz[x]=0;
     ctc[nrc].push_back(x);
     for(i=0; i<GT[x].size(); i++)
        if(viz[GT[x][i]])
            DFST(GT[x][i]);
 }

int main()
{
    citire();
    for(int i=1; i<=n; i++)
        if(!viz[i])
        DFS(i);
    //parcurg vec post de la dr la st
    for(int i=n; i>0; i--)
        if(viz[post[i]]==1) //post de i nevizitat in GT
            {
                //am identificat o comp noua tare conexa
                nrc++;
                DFST(post[i]);
            }
    afisare();
    return 0;
}