Cod sursa(job #3374095)

Utilizator Moriiandrei Morii Data 8 noiembrie 2026 17:38:05
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>
#define int long long
using namespace std;


int n,m;
vector<int>v[100001];
stack<int>st;
vector<int>M[100001];
vector<int>Mt[100001];
int viz[100001];
void dfs1(int nod)
  {
        viz[nod] = 1;
           for(auto i : M[nod])
           {
               if(!viz[i])
                dfs1(i);
           }
           st.push(nod);


  }
void dfs2(int nod,int col)
  {
       viz[nod] = 1;
       v[col].push_back(nod);
           for(auto i : Mt[nod])
           {
               if(!viz[i])
                dfs2(i,col);
           }

  }


signed main() {
freopen ("ctc.in","r",stdin);
freopen ("ctc.out","w",stdout);
       cin >> n >> m;
       for(int i = 1;i<=m;++i){

           int a,b;
           cin >> a >> b;
           M[a].push_back(b),Mt[b].push_back(a);

       }
      for(int i = 1;i<=n;++i)
      if(!viz[i])
      dfs1(i);

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

      int cc = 0;
      while(!st.empty())
    {
        int sus = st.top();
        st.pop();
        if(viz[sus])
            continue;

        cc++;
        dfs2(sus,cc);

    }

        cout << cc << endl;
        for(int i = 1;i<=cc;++i)
       {
           for(auto j : v[i])
            cout << j << " ";


           cout << endl;
       }




    return 0;
}