Cod sursa(job #3223476)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 13 aprilie 2024 12:19:38
Problema Componente biconexe Scor 64
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.92 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define MAXN 100000
#define MAXM 200000
#define DEBUG 0

using namespace std;

struct Edge{
  int a, b;
  bool solved = false;

  int getOther(int id){
    if(id == b)
      return a;
    return b;
  }
};

vector<vector<int>> v;
Edge e[MAXM];

vector<vector<int>> r;

int d[MAXN], l[MAXN];
stack<Edge> vert; // vert contains the edges that arrived last
int xval = 1;

void addComponent(int id, int child){
  int la, lb;
  r.push_back({});
  while(!vert.empty() && !(la == id && lb == child) && !(la == child && lb == id)){
    int a = vert.top().a, b = vert.top().b;
    vert.pop();

    if(a != la && a != lb)
      r[r.size() - 1].push_back(a);
    if(b != la && b != lb)
      r[r.size() - 1].push_back(b);
    la = a;
    lb = b;
  }
}

void dfs(int id){
  d[id] = xval ++;
  l[id] = d[id];

  int minv = d[id], nrc = 0;
  for(int i = 0; i < (int)v[id].size(); i ++){
    if(!e[v[id][i]].solved){
      int node = e[v[id][i]].getOther(id);
      e[v[id][i]].solved = true;

      if(d[node] == 0){
        vert.push(e[v[id][i]]);
        dfs(node);
        nrc ++;
      }
      if(l[node] >= d[id]){ // Avem 1 copil care nu poate ajunge mai sus de noi
        addComponent(id, node);
      }

      else if(l[node] < minv) // Avem 1 copil prin care putem ajunge si mai sus
          minv = l[node];
    }
  }
  l[id] = minv;

  // if(id == 0 && nrc > 1)
  //   addComponent(0);
}

int main(){
  int n, m;

  ifstream fin ("biconex.in");
  fin >> n >> m;
  v.resize(n); 
  
  for(int i = 0; i < m; i ++){
    int a, b;
    fin >> a >> b;
    e[i] = {a - 1, b - 1};
    v[a - 1].push_back(i);
    v[b - 1].push_back(i);
  }
  fin.close();

  dfs(0);

  ofstream fout ("biconex.out");
  fout << r.size() << "\n";
  for(int i = 0; i < (int)r.size(); i ++){
    for(int j = 0; j < (int)r[i].size(); j ++)
      fout << r[i][j] + 1 << ' ';
    fout << "\n";
  }
  fout.close();

  return 0;
}