Cod sursa(job #2461676)

Utilizator MortemPlaiasu Iulia-Silvia Mortem Data 25 septembrie 2019 22:29:09
Problema Componente biconexe Scor 100
Compilator cpp-32 Status done
Runda Arhiva educationala Marime 1.38 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>

using namespace std;

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

int n,m;
vector<int> v[100500];
bool vis[100500];

int disc[100500];
int low[100500];
int dCount;

struct edge
{
  int x,y;
};
stack<edge> s;

int rezC;
vector<int> rez[100500];



void specDFS(int nodR, int fath)
{
  vis[nodR]=true;
  disc[nodR]=low[nodR]=dCount;
  dCount++;
  for(vector<int>::iterator i=v[nodR].begin();i!=v[nodR].end();++i)
  {
    int elem= *i;
    if(fath==elem) continue;
    if(!vis[elem])
    {
      s.push({nodR,elem});
      specDFS(elem,nodR);
      low[nodR]=min(low[nodR],low[elem]);
      if(low[elem]>=disc[nodR])
      {
        while((s.top().x)!=nodR)
        {
          rez[rezC].push_back(s.top().y);
          s.pop();
        }
        rez[rezC].push_back(s.top().y);
        s.pop();
        rez[rezC].push_back(nodR);
        rezC++;
      }
    }
    else
      low[nodR]=min(low[nodR],disc[elem]);
  }
}

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]) specDFS(i,0);
  fout<<rezC<<"\n";
  for(int i=0;i<rezC;i++)
  {
    sort(rez[i].begin(),rez[i].end());
    for(vector<int>::iterator j=rez[i].begin();j!=rez[i].end();++j)
      fout<<(*j)<<" ";
    fout<<"\n";
  }
}