Cod sursa(job #3336327)

Utilizator MoryokaVlaviano Mario Moryoka Data 24 ianuarie 2026 15:55:45
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.19 kb
#include <vector>
#include <fstream>
#include <stack>

using namespace std;

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

vector<vector<int>> grI;
vector<vector<int>> grT;
vector<int> viz;
stack<int> st;

vector<vector<int>> cc(100005);


int nrComp = 0;

void dfs(int vf){
    viz[vf] = 1;
    for(int x : grI[vf]){
        if(!viz[x]){
            dfs(x);
        }
    }

    st.push(vf);
}

void dfsT(int vf, int index_c) {
  viz[vf] = 1;
  cc[index_c].push_back(vf);

  for(int x : grT[vf]){
    if(!viz[x]){
      dfsT(x, index_c);
    }
  }
}

int main(){
    int n, m;
    fin >> n >> m;
    grI.resize(n+1);
    grT.resize(n+1);

    viz.assign(n+1, 0);

    for(int i=1; i<=m; i++){
        int x, y;
        fin >> x >> y;

        grI[x].push_back(y);
        grT[y].push_back(x);
    }

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

    viz.assign(n+1, 0);

    while(!st.empty()){
        int vf = st.top();
        st.pop();

        if(viz[vf] != 1){
          dfsT(vf, nrComp);
          nrComp++;
        }
    }

    fout<<nrComp<<endl;
    for(int i = 0; i < nrComp; i++){
      for(int x : cc[i]){
        fout<<x<<" ";
      }
      fout<<endl;
    }
}