Cod sursa(job #2492294)

Utilizator spatarelDan-Constantin Spatarel spatarel Data 14 noiembrie 2019 14:42:39
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.54 kb
#include <stdio.h>
#include <algorithm>
#include <stack>
#include <vector>

const int MAX_N = 100000;
const int MAX_M = 200000;

struct Edge {
  int id;
  int u;
  int v;

  int biconnectedId;

  int other(int x) const {
    return u + v - x;
  }
};

std::vector<Edge*> edges[1 + MAX_N];
Edge allEdges[1 + MAX_M];
bool visited[1 + MAX_N];
int parent[1 + MAX_N];
int depth[1 + MAX_N];
int upLink[1 + MAX_N];

int biconnectedComponentCount;
std::vector<Edge*> biconnectedComponent[1 + MAX_M];
std::stack<Edge*> traversedEdges;

void dfs(int u) {
  visited[u] = true;
  for (Edge* e : edges[u]) {
    int v = e->other(u);
    if (v != parent[u]) {
      if (!visited[v]) {
        traversedEdges.push(e);
        //printf("<%d> ", e->id);
        parent[v] = u;
        depth[v] = depth[u] + 1;
        upLink[v] = depth[v];
        dfs(v);
        if (upLink[v] >= depth[u]) {
          // a new biconnected component has been detected
          biconnectedComponentCount++;
          while (e->biconnectedId == 0) {
            Edge* edge = traversedEdges.top();
            traversedEdges.pop();
            biconnectedComponent[biconnectedComponentCount].push_back(edge);
            edge->biconnectedId = biconnectedComponentCount;
          }
        }
        upLink[u] = std::min(upLink[u], upLink[v]);
      } else { // return edges
        if (depth[u] > depth[v]) {
          traversedEdges.push(e);
          //printf(">%d< ", e->id);
          upLink[u] = std::min(upLink[u], upLink[v]); // ???
        }
      }
    }
  }
}

int main() {
  freopen("biconex.in", "r", stdin);
  freopen("biconex.out", "w", stdout);
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 0; i < m; i++) {
    allEdges[i].id = i;
    scanf("%d%d", &allEdges[i].u, &allEdges[i].v);
    edges[allEdges[i].u].push_back(&allEdges[i]);
    edges[allEdges[i].v].push_back(&allEdges[i]);
  }
  biconnectedComponentCount = 0;
  for (int u = 1; u <= n; u++) {
    visited[u] = false;
    depth[u] = 0;
    upLink[u] = 0;
  }
  parent[1] = 0;
  depth[1] = 1;
  upLink[1] = 1;
  dfs(1);
  printf("%d\n", biconnectedComponentCount);
  for (int i = 1; i <= biconnectedComponentCount; i++) {
    std::vector<int> vertices;
    vertices.clear();
    for (Edge* e : biconnectedComponent[i]) {
      //printf("(%d-%d) ", e->u, e->v);
      vertices.push_back(e->u);
      vertices.push_back(e->v);
    }
    std::sort(vertices.begin(), vertices.end());
    vertices.resize(std::unique(vertices.begin(), vertices.end()) - vertices.begin());
    for (int v : vertices) {
      printf("%d ", v);
    }
    printf("\n");
  }
  return 0;
}