Cod sursa(job #3368929)

Utilizator Moriiandrei Morii Data 16 octombrie 2026 16:37:03
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.39 kb
#include <bits/stdc++.h>

using namespace std;

int n,m;


vector<int>M[100001];
vector<int>Mt[100001];
stack<int>st;

vector<vector<int>>ans;

vector<int>temp;




int viz[100001];
void dfs(int nod)
  {
      viz[nod] = 1;
       for(auto i : M[nod])
                if(!viz[i])
                dfs(i);

       st.push(nod);

  }

void dfs2(int nod)
   {
       temp.push_back(nod);
         viz[nod] = 1;

       for(auto i : Mt[nod])
          if(!viz[i])
            dfs2(i);


   }

int main()
{    freopen("ctc.in","r",stdin);
      freopen("ctc.out","w",stdout);

         cin >> n >> m;
               while(m--)
    {
        int x,y;
        cin >> x >> y;
        M[x].push_back(y);
        Mt[y].push_back(x);
    }
     for(int i = 1;i<=n;++i)
   if(!viz[i])
      dfs(i);

      for(int i = 1;i<=n;++i)
         viz[i] = 0;

         while(!st.empty())
           {
               int nod = st.top();
               st.pop();
               if(!viz[nod])
                 {
                    temp.clear();
                    dfs2(nod);
                   ans.push_back(temp);

                 }

           }
  cout << ans.size() << endl;
  for(int i = 0;i<ans.size();++i)
      {
          for(int j = 0;j<ans[i].size();++j)
            cout << ans[i][j] << " ";


          cout << endl;
      }


    return 0;
}