Cod sursa(job #2198067)

Utilizator PostMaloneLiurca Daniel PostMalone Data 23 aprilie 2018 15:42:10
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.83 kb
#include <fstream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int kNmax = 100005;
const int NIL = -1;
#define Min(a, b)  ((a) < (b) ? (a) : (b))

class Task {
 public:
	void solve() {
		read_input();
		dfn.resize(n + 1), dfn.assign(n + 1, -1);
		low.resize(n + 1);
		dfs(1, 0, 0);
		print_output();
	}

 private:
	int n;
	int m;

	vector <int> adj[kNmax], dfn, low;
 
	vector <vector <int> > C;
 
	stack <pair <int, int> > stk;

	struct Edge {
		int x;
		int y;
	};

	void read_input() {
		ifstream fin("biconex.in");
		fin >> n >> m;
		for (int i = 1, x, y; i <= m; i++) {
			fin >> x >> y;
			adj[x].push_back(y);
			adj[y].push_back(x);
		}
		fin.close();
	}

	void f (const int a, const int b) {
		/*
		TODO: Gasiti muchiile critice ale grafului neorientat stocat cu liste
		de adiacenta in adj.
		*/

		vector <int> conexe;
		int x, y;

		do {
			x = stk.top().first;
			y = stk.top().second;
			stk.pop();
			conexe.push_back(x), conexe.push_back(y);
		} while (a != x || b != y);

		C.push_back(conexe);
	}


	void dfs(const int n, const int fn, int number) {
		vector <int>::iterator it;

		dfn[n] = low[n] = number;
 		for (it = adj[n].begin(); it != adj[n].end(); ++ it) {
			if (*it == fn)   continue ;
			if (dfn[*it] == -1) {
				stk.push( make_pair(n, *it) );
				dfs(*it, n, number + 1);
				low[n] = Min(low[n], low[*it]);
				if (low[*it] >= dfn[n])
					f(n, *it);
			} else
				low[n] = Min(low[n], dfn[*it]);
		}
	}

	void print_output() {
		ofstream out("biconex.out");

		for (size_t i = 0; i < C.size(); ++ i) {
			sort(C[i].begin(), C[i].end());
			C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
			for (size_t j = 0; j < C[i].size(); ++ j)
				out << C[i][j] << " ";
				out << "\n";
		}
		out.close();
	}
};

int main() {
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}