Cod sursa(job #2922372)

Utilizator petru-robuRobu Petru petru-robu Data 8 septembrie 2022 09:14:38
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.45 kb
#include <bits/stdc++.h>
using namespace std;
#define MAXN 100005

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

int N, M, index_=0;
vector<int> G[MAXN], idx, lowlink, in_stack, componenta;
vector< vector<int> > Componente;
stack<int> S;

void read()
{
  fin>>N>>M;
  for(int i=1; i<=M; i++)
  {
    int x, y; fin>>x>>y;
    G[x-1].push_back(y-1);
  }
  fin.close();
}

void print()
{
  fout<<Componente.size()<< '\n';
  for(size_t i=0; i < Componente.size(); i++)
  {
    for(size_t j=0; j< Componente[i].size(); j++)
      fout<<Componente[i][j] + 1 <<' ';
    fout<<'\n';
  }
  fout.close();
}

void tarjan(int x)
{
  idx[x] = lowlink[x] = index_;
  index_++;
  S.push(x);
  in_stack[x] = 1;

  for(auto& vecin: G[x])
  {
    if(idx[vecin] == -1)
    {
      tarjan(vecin);
      lowlink[x] = min(lowlink[x], lowlink[vecin]);
    }
    else
      if(in_stack[vecin])
        lowlink[x] = min(lowlink[x], lowlink[vecin]);
  }

  if(idx[x] == lowlink[x])
  {
    componenta.clear();
    int node;
    do
    {
      node = S.top();
      S.pop();
      in_stack[node] = 0;
      componenta.push_back(node);
    } while(node != x);

    Componente.push_back(componenta);
  }
}


int main()
{
  read();

  idx.resize(N); idx.assign(N, -1);
  lowlink.resize(N);
  in_stack.resize(N); in_stack.assign(N, -1);

  for(int i=0; i<N; i++)
    if(idx[i] == -1)
      tarjan(i);

  print();
  return 0;
}