Cod sursa(job #2601604)

Utilizator usermeBogdan Cretu userme Data 14 aprilie 2020 19:42:30
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.28 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

const int len = 100001;
int low[len], depth[len];
vector<int> g[len], sol[len];

bool visited[len];

stack<int> s; 

int n, m, x, y, count;

void dfs(int node, int parent) {
	depth[node] = depth[parent] + 1;
	low[node] = depth[node];

	visited[node] = true;

	s.push(node);

	for (int i = 0; i < g[node].size(); i++) {
		int elem = g[node][i];

		if (elem != parent) {
			if (visited[elem]) {
				low[node] = low[node] < depth[elem] ? low[node] : depth[elem];
				continue;
			}

			dfs(elem, node);

			low[node] = low[node] < low[elem] ? low[node] : low[elem];

			if (low[elem] >= depth[node]) {
				int top;
				do {
					top = s.top();

					sol[count].push_back(top);

					s.pop();				
				} while (top != elem);

				sol[count++].push_back(node);
			}
		}
	}

}

int main() {

	for (int i = 0; i < len; i++) {
		visited[i] = false;
	}

	ifstream f("biconex.in");
	ofstream h("biconex.out");

	f >> n >> m;
	while (m) {
		m = m - 1;

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

	for (int i = 1; i <= n; i++) {
		if (visited[i] == false) {
			dfs(i, 0);
		}
	}

	h << count << "\n";

	for (int i = 0; i < count; i++) {
		for (int j = 0; j < sol[i].size(); j++) {
			h << sol[i][j] << " ";
		}

		h << "\n";
	}

}