Cod sursa(job #2686544)

Utilizator sabinandreiBocan Sabin Andrei sabinandrei Data 19 decembrie 2020 11:36:58
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.95 kb
// Biconerxe.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include<fstream>
#include<bitset>
#include<vector>
#include<algorithm>

using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");

vector<int> v[100001];
bitset<100001> viz;
int low[100001];
int tata[100001];
int dft[100001];
int cnt = 0;
vector<int> st;
vector<vector<int>> sol;


void get_sol(int x, int y) {
	vector<int> aux;
	sol.push_back(aux);
	while (st.back() != y) {
		sol[sol.size() - 1].push_back(st.back());
		st.pop_back();
	}
	st.pop_back();
	sol[sol.size() - 1].push_back(x);
	sol[sol.size() - 1].push_back(y);
}

void dfs(int x, int f) {
	dft[x] = low[x] = ++cnt;
	for (auto it : v[x]) {
		if (it != f) {
			if (!dft[it]) {
				st.push_back(it);
				dfs(it, x);

				low[x] = min(low[it], low[x]);
				if (low[it] >= dft[x])
					get_sol(x, it);
			}
			else {
				low[x] = min(low[x], dft[it]);
			}
		}
	}
}



int main() {
	int n, m;
	in >> n >> m;
	for (int i = 1; i <= m; i++) {
		int x, y;
		in >> x >> y;
		v[x].push_back(y);
		v[y].push_back(x);
	}
	dfs(1, 0);
	out << sol.size() << '\n';
	for (int i = 0; i < sol.size(); i++) {
		for (int j = 0; j < sol[i].size(); j++) {
			out << sol[i][j] << ' ';
		}
		out << '\n';
	}
}

// Run program: Ctrl + F5 or Debug > Start Without Debugging menu
// Debug program: F5 or Debug > Start Debugging menu

// Tips for Getting Started: 
//   1. Use the Solution Explorer window to add/manage files
//   2. Use the Team Explorer window to connect to source control
//   3. Use the Output window to see build output and other messages
//   4. Use the Error List window to view errors
//   5. Go to Project > Add New Item to create new code files, or Project > Add Existing Item to add existing code files to the project
//   6. In the future, to open this project again, go to File > Open > Project and select the .sln file