Cod sursa(job #3223505)

Utilizator Remus.RughinisRemus Rughinis Remus.Rughinis Data 13 aprilie 2024 12:38:13
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.26 kb
#include <iostream>
#include <algorithm>
#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 = -1, lb = -1;
  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 ++){
    sort(r[i].begin(), r[i].end()); 
  
    // use unique() to bring all the duplicates to end 
    // and get the ierator for the modified vector 
    auto it 
        = unique(r[i].begin(), r[i].end()); 
  
    // Use erase method  to remove all the duplicates 
    // from the vector 
    r[i].erase(it, r[i].end()); 
    for (auto& element : r[i]) { 
        fout << element + 1 << " "; 
    } 
    fout << "\n";
  }
  fout.close();

  return 0;
}