Cod sursa(job #1166713)

Utilizator toranagahVlad Badelita toranagah Data 3 aprilie 2014 19:20:23
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.46 kb
#include <algorithm>
#include <bitset>
#include <fstream>
#include <iostream>
#include <vector>
using namespace std;

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

typedef pair<int, int> pii;
#define x first
#define y second

const int MAX_N = 100100;

int N, M;
vector<int> graph[MAX_N];
bitset<MAX_N> vis;
vector<pii> st;
vector<vector<int>> ans;
int depth[MAX_N], lowest[MAX_N];

void dfs(int node);
void flush_biconex(pii e);

int main() {
  fin >> N >> M;
  for (int i = 1, a, b; i <= M; i += 1) {
    fin >> a >> b;
    graph[a].push_back(b);
    graph[b].push_back(a);
  }
  dfs(1);

  fout << ans.size() << '\n';
  for (auto i: ans) {
    for (auto j: i) {
      fout << j << ' ';
    }
    fout << '\n';
  }
}

void dfs(int node) {
  vis[node] = 1;

  lowest[node] = depth[node];
  for (auto x: graph[node]) {
    if (vis[x]) {
      lowest[node] = min(lowest[node], depth[x]);
      continue;
    }

    depth[x] = depth[node] + 1;
    st.push_back(make_pair(node, x));
    dfs(x);

    if (lowest[x] >= depth[node])
      flush_biconex(make_pair(node, x));
    lowest[node] = min(lowest[node], lowest[x]);
  }
}

inline void flush_biconex(pii e) {
  ans.push_back(vector<int>());
  vector<int> &c = ans.back();
  while (st.back() != e) {
    c.push_back(st.back().x);
    c.push_back(st.back().y);
    st.pop_back();
  }
  c.push_back(st.back().x);
  c.push_back(st.back().y);
  st.pop_back();

  sort(c.begin(), c.end());
  c.resize(unique(c.begin(), c.end()) - c.begin());
}