Cod sursa(job #2406145)

Utilizator dragos.unguruUnguru Dragos-Gabriel dragos.unguru Data 15 aprilie 2019 13:53:34
Problema Componente biconexe Scor 90
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 3.3 kb
#include <fstream>
#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

const int kNmax = 100005;
#define MIN(a, b) ((a < b) ? a : b)

class Task {
 public:
	void solve() {
		read_input();
		print_output(get_result());
	}

 private:
	int n;
	int m;
	vector<int> adj[kNmax];

	struct Edge {
		int x;
		int y;

		Edge(int _x, int _y):
			x(_x),
			y(_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 tarjan(int u, vector<int>& discovery_time, vector<int>& low,
				vector<int>& parent, stack<Edge>& st, vector<vector<Edge>>& sol) {
		
		static int discovered_time = 0;
		int children_no = 0;

		discovery_time[u] = ++discovered_time;
		low[u] = discovered_time;

		for (int i = 0; i < adj[u].size(); ++i) {
			int v = adj[u][i];
			
			if (discovery_time[v] == -1) {
				children_no++;
				parent[v] = u;

				st.push(Edge(u, v));
				tarjan(v, discovery_time, low, parent, st, sol);

				low[u] = MIN(low[u], low[v]);

				if (((parent[u] == -1) && (children_no > 1)) || ((parent[u] != -1) && (low[v] >= discovery_time[u]))) {
				vector<Edge> buffer;

                while (st.top().x != u && st.top().y != v) {
					buffer.push_back(Edge(st.top()));
                    st.pop(); 
                }
				buffer.push_back(Edge(st.top()));
				sol.push_back(buffer);
				buffer.clear();
                st.pop();
            	}
			}
			else if (v != parent[u]) {
				low[u] = MIN(low[u], discovery_time[v]);
			}
		}		
		// vector<Edge> buffer;
		// while (!st.empty()) {
		// 	buffer.push_back(Edge(st.top()));
		// 	st.pop();
		// }
		// sol.push_back(buffer);
	}

	vector<vector<Edge>> get_result() {
		vector<int> parent(n + 1, -1);
		vector<int> low(n + 1);
		vector<int> discovery_time(n + 1, -1);
		vector<Edge> buffer;
		stack<Edge> st;
		vector<vector<Edge>> sol;

		// cout << "n = " << n << "\n";
		// cout << "m = " << m << "\n";

		// for (int i = 1; i < n; ++i) {
		// 	cout << "Adj list for node: " << i << " -> ";
		// 	for (int j = 0; j < adj[i].size(); ++j) {
		// 		cout << adj[i][j] << " ";
		// 	}
		// 	cout << "\n";
		// }

		for (int i = 1; i <=n; ++i) {
			if (discovery_time[i] == -1) {
				tarjan(i, discovery_time, low, parent, st, sol);
			}
		}

		while (!st.empty()) {
			buffer.push_back(Edge(st.top()));
			st.pop();
		}
		sol.push_back(buffer);

		return sol;
	}


	void print_output(const vector<vector<Edge>>& result) {
		ofstream fout("biconex.out");
		vector<bool> buf(n + 1, false);

		fout << result.size() << '\n';
		for (int i = 0; i < int(result.size()); i++) {
			for (int j = 0; j < result[i].size(); ++j) {
				if (buf[result[i][j].x] == false) {
					fout << result[i][j].x << " ";
					buf[result[i][j].x] = true;
				}
				if (buf[result[i][j].y] == false) {
					fout << result[i][j].y << " ";
					buf[result[i][j].y] = true;
				}
				// fout << result[i][j].x << " " << result[i][j].y << " ";
			}
			fill(buf.begin(), buf.end(), false);
			fout << "\n";
		}
		fout.close();
	}
};

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