Cod sursa(job #2422229)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 17 mai 2019 23:30:25
Problema Componente biconexe Scor 10
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.65 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <vector>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");

int n,m;
std::vector<int> v[100500];

struct edge
{
  int x,y;  
};

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

std::vector<int> rez[100500];
int rezc;
int countt;

void findSol(int x)
{
  rezc++;
  rez[rezc-1]=std::vector<int>();
  rez[rezc-1].push_back(s.top().y);
 // std::cout<<s.top().y<<" ";
  while(!s.empty()&& s.top().x!=x)
  {
    rez[rezc-1].push_back(s.top().x);
 //   std::cout<<s.top().x<<" ";
    s.pop();
  }
  if(!s.empty())
    s.pop();
  rez[rezc-1].push_back(x);
//  std::cout<<x<<" ";
 // std::cout<<"\n";
}

void specDFS(int u)
{
  vis[u]=true;
  low[u]=disc[u]=++countt;
  
 // std::cout<<u<<"\n";
  int children = 0;
  for(int i=0;i<v[u].size();i++)
  {
    int elem = v[u][i];
    if(!vis[elem])
    {
      children++;
      root[elem]=u;
      s.push({u,elem});
      specDFS(elem);
      
      low[u]=std::min(low[u],low[elem]);
      
      if(children >1 && root[u]==0)
      {
        findSol(u);
        findSol(u);
      }
      else if(root[u]!= 0 && low[elem]>= disc[u])
        findSol(u);
    }
    else if(elem!=root[u])
      low[u]=std::min(low[u],disc[elem]);
  }
//  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);
    v[k].push_back(j);
  }
  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";
  }
}