Cod sursa(job #2605831)

Utilizator Chr1styDescultu Cristian Chr1sty Data 25 aprilie 2020 22:29:32
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.48 kb
#include <bits/stdc++.h>
#define Edge pair<int, int>
using namespace std;


const int kNmax = 100005;

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

private:
	int n;
	int m;
	vector<int> adj[kNmax];
	vector<int> idx;
	vector<int> low_link;
	vector<int> cut_vertex;
	vector<int> parent;
	vector<int> is_cv;
    vector<vector<int>> biconex;

	void read_input() {
		ifstream fin("biconex.in");
		fin >> n >> m;
		idx = vector<int>(n + 1, -1);
		low_link = vector<int>(n + 1, 0);
		parent = vector<int> (n + 1, 0);
		is_cv = vector<int> (n + 1, 0);
		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 bicx_elem_function() {
		int curr_start = 0;

		for (int i = 1; i <= n; ++i) {
			if (idx[i] == -1) {
				parent[i] = 0;
				dfs(i, curr_start);
			}
		}
	}

	void dfs(int nod, int &curr_start) {
		
		curr_start++;
		idx[nod] = curr_start;
		low_link[nod] = curr_start;
		int children = 0;
		for (auto &neigh : adj[nod]) {
			if (idx[neigh] == -1) {
				parent[neigh] = nod;
				children++;
				dfs(neigh, curr_start);

				low_link[nod] = std::min(low_link[nod], low_link[neigh]);

				if (low_link[neigh] >= idx[nod]) {
					biconex_function(Edge(nod, neigh));
				}
			} else {
				if (neigh != parent[nod]) {
					low_link[nod] = std::min(low_link[nod], idx[neigh]);
				}
			}
		}
	}

    void biconex_function(Edge edge) {
        vector<int> bicx;
        Edge curr_edge = Edge(-1, -1);
        while(curr_edge != edge) {
            bicx.push_back(curr_edge.first);
            bicx.push_back(curr_edge.second);
        }

        sort(bicx.begin(), bicx.end());
        auto it = unique(bicx.begin(), bicx.end());
        bicx.erase(it, bicx.end());
        biconex.push_back(bicx);
    }

	vector<vector<int>> get_result() {
		bicx_elem_function();
		/*
		TODO: idxi nodurile critice ale grafului neorientat stocat cu liste
		de adiacenta in adj.
		*/
		return biconex;
	}

	void print_output(const vector<vector<int>>& result) {
		ofstream fout("biconex.out");
		for (int i = 0; i < biconex.size(); ++i) {
            for (auto &it : biconex[i]) {
                fout << it << ' ';
            }
            fout << '\n';
        }
		fout.close();
	}
};

// Please always keep this simple main function!
int main() {
	// Allocate a Task object on heap in order to be able to
	// declare huge static-allocated data structures inside the class.
	Task *task = new Task();
	task->solve();
	delete task;
	return 0;
}