Cod sursa(job #3223372)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 13 aprilie 2024 11:07:46
Problema Componente biconexe Scor 46
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.71 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<int> vert;
int xval = 1;

void addComponent(int idp){
  r.push_back({});
  while(vert.top() != idp){
    r[r.size() - 1].push_back(vert.top());
    vert.pop();
  }
  r[r.size() - 1].push_back(vert.top());
}

int dfs(int id){
  if(DEBUG)
    printf("%d %d %d\n", id + 1, d[id], l[id]);
  if(d[id] != 0)
    return 0;
  d[id] = xval ++;
  l[id] = d[id];

  vert.push(id);

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

      nrc += dfs(node);
      if(l[node] >= d[id]){ // Avem 1 copil care nu poate ajunge mai sus de noi
        addComponent(id);
      }

      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);

  return 1;
}

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 < r.size(); i ++){
    for(int j = 0; j < r[i].size(); j ++)
      fout << r[i][j] + 1 << " ";
    fout << "\n";
  }
  fout.close();

  return 0;
}