Cod sursa(job #1604151)

Utilizator TeodorCotetCotet Teodor TeodorCotet Data 17 februarie 2016 23:51:18
Problema Componente biconexe Scor 100
Compilator cpp Status done
Runda Arhiva educationala Marime 2.6 kb
#include <iostream>
#include <fstream>
#include <stack>
#include <bitset>
#include <vector>
#include <algorithm>

using namespace std;

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

#define pair pair<int,int>

const int NMAX = 100000;
const int MMAX = 200000;

int n; int m;

vector<int> g[NMAX + 1];

vector<int> low(NMAX + 1, 0);
vector<int> lev(NMAX + 1, -1);

stack<pair> st;

vector< vector<int> > comp;
bitset<NMAX + 1> articulate;

vector<int> ret(NMAX + 1, 0);

int nrComp;

void read(vector<int>* g, int& n, int& m) {

	fin >> n >> m;
	for(int i = 1; i <= m; ++i) {

		int x; int y; 
		fin >> x >> y;

		g[x].push_back(y);
		g[y].push_back(x);
	}
}

void getComponents(stack<pair>& st, int nodeL, int nodeR) {

	comp.push_back(vector<int>(0));

	int x; int y;
	do {

		x = st.top().first;
		y = st.top().second;
		comp[nrComp].push_back(x);
		comp[nrComp].push_back(y);
		st.pop();

	} while(st.empty() == false && !(x == nodeL && y == nodeR));

	nrComp++;
}

void dfs(int node, int father, int level) {

	lev[node] = low[node] = level;

	for(int x : g[node]) {
		if(x == father) continue; 
		
		if(lev[x] == -1) {

			st.push({node, x}); //bagam muchiile in ordinea viztarii

			dfs(x, node, level + 1);
			low[node] = min(low[x], low[node]); //pot sa ma intorc pe arbore in jos si apoi pe o muchie de intoarcere

			if(low[x] >= lev[node])  //la fii radacinii tot timpul intra low[fiu] > lev[radacina]
				articulate[node] = true, getComponents(st, node, x); //tot subarborele e o componenta biconexa

				/* daca dintr-un fiu al nodului curent nu putem ajunge pe arbore in jos si apoi pe o muhcie de intoarcere
					la un nod mai sus de nodul curent, insemna ca nodul curent este punct de articulatie
					(deconecteaza fiul + subarborele fiului fata de parinte) 
				Se pastreaza muchiile in ordinea parcurgerii. Componenta biconexa e formata din nodurile muchiilor dintre 2 puncte de 
				articulatie. Gasim punct de articulatie => golim stiva si formam componenta
					*/

		} else //e muchie de intoarcere, low e setat direct
			low[node] = min(low[node], lev[x]);
	}
}


void print() {

	fout << nrComp << '\n';

	for(vector<int> v : comp) {
		sort(v.begin(), v.end());

		v.erase(unique(v.begin(), v.end()) , v.end());

		//unique scoate elementele duplicate, dar nu face resize, returneaza adresa urmatorului element dupa ultimul
		//erase sterge intervalul specificiat inclusiv

		for(int x : v)
			fout << x << ' ';
		fout << '\n';
	}
}

int main() {

	read(g, n, m);
	dfs(1, 0, 0);
	print();

	return 0;
}