Cod sursa(job #3275437)

Utilizator Petru_77Panait Mihai-Petru Petru_77 Data 10 februarie 2025 16:57:48
Problema Componente tare conexe Scor 60
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
 #include <fstream>
 #include <vector>
 using namespace std;
 ifstream in("ctc.in");
 ofstream out("ctc.out");

  vector<int> direct[100001];
  vector<int> invers[100001];
  int vizd[100001], vizi[100001], comp[100001];

  void dfs(int x, vector<int> v[100001], int viz[100001])
  {
    viz[x] = 1;
    int k = v[x].size();
    for(int i = 0; i < k; i++)
    {
      if(viz[ v[x][i] ] == 0  && comp[ v[x][i] ] == 0 )
      {
        dfs( v[x][i], v, viz);
      }
    }
  }


int main()
{
   int n , m;
   in >> n >> m;
   for(int i = 1 ; i <= m; i ++)
   {
     int x , y; // x->y
     in >> x >> y;
     direct[x].push_back(y);
     invers[y].push_back(x);
   }
   int nrc=0;
   for(int i = 1; i <= n; i++)
   {
   if(comp[i]==0)
   {
     nrc++;

     dfs(i, direct, vizd);
     dfs(i, invers, vizi);

     for(int j = 1 ; j <= n; j++)
     {
       if(vizd[j] == 1 && vizi[j] == 1)
       {
         comp[j] = nrc;
       }

        vizd[j] = vizi[j] = 0;
     }

   }
   }


   out<<nrc<<'\n';
   for(int i = 1; i <= nrc; i++)
   {
     for(int j = 1; j <= n; j++)
     {
       if(comp[j] == i)
       {
         out << j << " ";
       }
     }
     out << "\n";
   }


    return 0;
}