Cod sursa(job #2013669)

Utilizator TincaMateiTinca Matei TincaMatei Data 22 august 2017 00:47:39
Problema Componente biconexe Scor 46
Compilator cpp Status done
Runda Arhiva educationala Marime 1.36 kb
#include <bits/stdc++.h>

using namespace std;

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

struct Edge {
  int a, b;
	int other(int nod) {
	  return a ^ b ^ nod;
	}
} e[MAX_M];

vector<int> graph[1+MAX_N];
int low[1+MAX_N], h[1+MAX_N];
vector<vector<int> > comp;
int st[MAX_M], top;

int min(int a, int b) {
  if(a < b)
	  return a;
	return b;
}

void dfs(int nod, int fatherEdge) {
	for(auto it: graph[nod]) {
	  int son = e[it].other(nod);
		if(low[son] == 0) {
		  low[son] = h[son] = h[nod] + 1;
			st[top++] = it;
			dfs(son, it);
			low[nod] = min(low[nod], low[son]);
			if(low[son] >= h[nod]) {
			  vector<int> bic;
				while(top > 0 && st[top - 1] != fatherEdge) {
				  --top;
					int mc = st[top];
					bic.push_back(e[mc].a);
					bic.push_back(e[mc].b);
				}
				sort(bic.begin(), bic.end());
				bic.resize(unique(bic.begin(), bic.end()) - bic.begin());
				comp.push_back(bic);
			}
		} else if(it != fatherEdge)
			low[nod] = min(low[nod], h[son]);
	}
}

int main() {
  int n, m;
	ifstream fin("biconex.in");
	ofstream fout("biconex.out");
	fin >> n >> m;
	for(int i = 0; i < m; ++i) {
	  fin >> e[i].a >> e[i].b;
		graph[e[i].a].push_back(i);
		graph[e[i].b].push_back(i);
	}

	low[1] = h[1] = 1;
	dfs(1, -1);

	fout << comp.size() << '\n';
	for(auto it: comp) {
	  for(int i = 0; i < it.size(); ++i)
		  fout << it[i] << ' ';
		fout << '\n';
	}
	return 0;
}