Cod sursa(job #3230225)

Utilizator elena_dElena Dulgheru elena_d Data 19 mai 2024 23:58:08
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.34 kb
#include <bits/stdc++.h>

using namespace std;

ifstream fin("biconex.in");
ofstream fout("biconex.out");

#define NMAX 100000

vector <int> g[NMAX + 2];
int viz[NMAX + 2];
int highestNode[NMAX + 2];

int nodes_stack[NMAX + 2];

int stack_top;
int nrComp;
int currTime;

void rst(int n) {
	for (int i = 1; i <= n; ++i)
		highestNode[i] = viz[i] = 0;
		
	currTime = 0;
	stack_top = 0;
}

void dfs(int node, int parent, int print) {
	
  	highestNode[node] = parent;
	viz[node] = ++currTime;
	nodes_stack[++stack_top] = node;

	for (int newNode : g[node]) {
		if (newNode == parent) 
			continue;

		if (!viz[newNode]) {
			dfs(newNode, node, print);

			if (viz[highestNode[newNode]] < viz[highestNode[node]])
				highestNode[node] = highestNode[newNode];

			if (highestNode[newNode] == node) {
				++nrComp;

				if (print > 0) {
					while (stack_top > 0 && nodes_stack[stack_top] != newNode) {
						fout << nodes_stack[stack_top] << " ";
						--stack_top;
					}
					--stack_top;
					fout << newNode << " " << node << "\n";
				}
			}
		} else {
			if (viz[newNode] < viz[highestNode[node]])
				highestNode[node] = newNode;
		}
	}
}

int main() {
	int n, m;

	fin >> n >> m;

	for (int i = 1; i <= m; ++i) {
		int x, y;
		fin >> x >> y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	dfs(1, 0, 0);
	fout << nrComp << "\n";

	rst(n);
	dfs(1, 0, 1);

  return 0;
}