Cod sursa(job #2422215)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 17 mai 2019 21:14:28
Problema Componente tare conexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>

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

std::vector<int> v[100500];
bool vis[100500];
bool ins[100500];
std::stack<int> s;
int disc[100500];
int low[100500];

int n,m;
int countt;
std::vector<int> rez[100500];
int rezc;
void specDFS(int u)
{
  vis[u]=true;
  ins[u]=true;
  s.push(u);
  if(disc[u]==0)
    disc[u]=low[u]=++countt;
  //std::cout<<u<<"\n";
  for(int i=0;i<v[u].size();i++)
  {
    int elem=v[u][i];
    if(!vis[elem])
    {
      specDFS(elem);
      low[u]=std::min(low[u],low[elem]);
    }
    else if(vis[elem]&& ins[elem] )
      low[u]=std::min(low[u],disc[elem]);
  }
  if(disc[u]==low[u])
  {
    rezc++;
    rez[rezc-1]= std::vector<int>();
    while(s.top()!=u)
    {
      rez[rezc-1].push_back(s.top());
      ins[s.top()]=false;
      s.pop();
    }
    rez[rezc-1].push_back(s.top());
    s.pop();
    ins[u]=false;
  }
 // std::cout<<"end:"<<u<<"\n";
}

int main()
{
  fin>>n>>m;
  for(int i=0;i<m;i++)
  {
    int j,k;
    fin>>j>>k;
    v[j].push_back(k);
  }
  for(int i=1;i<=n;i++)
  {
    if(vis[i]) continue;
    specDFS(i);
  }
  fout<<rezc<<"\n";
  for(int i=0;i<rezc;i++)
  {
    for(int j=0;j<rez[i].size();j++)
      fout<<rez[i][j]<<" ";
    fout<<"\n";
  }
}