Cod sursa(job #3275435)

Utilizator Petru_77Panait Mihai-Petru Petru_77 Data 10 februarie 2025 16:54:23
Problema Componente tare conexe Scor 30
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.26 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)
      {
        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++;
     for(int j = 1 ; j <= n; j++)
     {
       vizd[j] = vizi[j] = 0;
     }
     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;
       }
     }

   }
   }


   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;
}