Cod sursa(job #1686425)

Utilizator BrandonChris Luntraru Brandon Data 12 aprilie 2016 11:27:41
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 1.78 kb
#include <fstream>
#include <vector>
#include <algorithm>

#define Pe pair <int, int>
#define mp make_pair
#define fi first
#define se second
using namespace std;

const int MaxN = 100005;

ifstream cin("biconex.in");
ofstream cout("biconex.out");

vector <Pe> Bicon;
vector <int> G[MaxN], partial_ans;
vector <vector <int>> Ans;

int depth[MaxN], highest[MaxN];
int n, m;

void BuildBicon(int end1, int end2) {
  partial_ans.clear();

  int n1 = Bicon.back().fi;
  int n2 = Bicon.back().se;
  Bicon.pop_back();
  partial_ans.push_back(n1);
  partial_ans.push_back(n2);

  while(!Bicon.empty() and (n1 != end1 or n2 != end2)) {
    n1 = Bicon.back().fi;
    n2 = Bicon.back().se;
    Bicon.pop_back();
    partial_ans.push_back(n1);
    partial_ans.push_back(n2);
  }

  sort(partial_ans.begin(), partial_ans.end());
  partial_ans.erase(unique(partial_ans.begin(), partial_ans.end()), partial_ans.end());
  Ans.push_back(partial_ans);
}

void Dfs(int node = 1, int level = 1, int father = 0) {
  depth[node] = level;
  highest[node] = level;

  for(auto nxt: G[node]) {
    if(father == nxt) {
      continue;
    }

    if(!depth[nxt]) {
      Bicon.push_back(mp(node, nxt));
      Dfs(nxt, level + 1, node);
      highest[node] = min(highest[node], highest[nxt]);

      if(highest[nxt] >= level) {
        BuildBicon(node, nxt);
      }
    }
    else {
      highest[node] = min(highest[node], depth[nxt]);
    }
  }
}

int main() {
  cin >> n >> m;

  for(int i = 1; i <= m; ++i) {
    int a, b;
    cin >> a >> b;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  Dfs();

  cout << Ans.size() << '\n';

  for(auto ans: Ans) {
    for(auto it: ans) {
      cout << it << ' ';
    }

    cout << '\n';
  }
  return 0;
}