Cod sursa(job #2404490)

Utilizator Petrisor98Anghel Ionut Petrisor Petrisor98 Data 12 aprilie 2019 21:23:32
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.24 kb
#include <fstream>		
#include <vector>
#include <algorithm>	
	
#define nmax 100100
	
using namespace std;
		
vector<int> adj[nmax];
vector<int> sol[2 * nmax];
	
vector<pair<int,int>> s;
	

int low[nmax], discovered[nmax], visited[nmax];	
int nr;
		
void dfs(int nod, int pre) {
	low[nod] = discovered[nod] = discovered[pre] + 1;
	visited[nod] = 1;
	
	for (auto i = adj[nod].begin(); i != adj[nod].end(); i++) {
			if (!visited[*i]) {	
				s.push_back(make_pair(nod, *i));
				dfs(*i, nod);
		
				low[nod] = min(low[nod], low[*i]);
				
				if (low[*i] >= discovered[nod]) {	
					nr++;	
					while (s.back().first != nod) {
						sol[nr].push_back(s.back().second);
						s.pop_back();
					}
	
					sol[nr].push_back(nod);
					sol[nr].push_back(s.back().second);
					s.pop_back();	
				}

			} else {
				low[nod] = min(discovered[*i], low[nod]);
			}
	}
	
}		
	
	
	
int main() {
	int m, n, x, y, i;
	
	ifstream read("biconex.in");
	ofstream write("biconex.out");
	
	read >> n >> m;
	
	while (m--) {	
		read >> x >> y;
	
		adj[x].push_back(y);
		adj[y].push_back(x);
	}
	
	dfs(1, 0);

	write << nr << '\n';
	
	for(i = 1; i <= nr; i++) {	
		for(auto it = sol[i].begin(); it != sol[i].end(); it++) {
			write << *it << ' ';
		}

		write<<'\n';
	
	}	
	
	return 0;	
}