Cod sursa(job #2406464)

Utilizator Petrisor98Anghel Ionut Petrisor Petrisor98 Data 15 aprilie 2019 19:24:56
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>		
#include <vector>
#include <algorithm>	
	
using namespace std;

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

const int kNmax = 100005;
				
vector<int> adj[kNmax];
vector<int> sol[2 * kNmax];	
vector<pair<int,int>> s;
		
int low[kNmax], discovered[kNmax], visited[kNmax];		
int nrComp;
	
		
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]) {	
					 nrComp++;
					 
					while (s.back().first != nod) {
						sol[nrComp].push_back(s.back().second);
						s.pop_back();
					}
	
					sol[nrComp].push_back(nod);
					sol[nrComp].push_back(s.back().second);
					s.pop_back();	
				}
				
			} else {
				low[nod] = min(discovered[*i], low[nod]);
	
			}
	}	
}		
	
	
int main() {
	
	int m, n, x, y, i;
	
	f >> n >> m;
	
	while (m) {	
	    f >> x >> y;
		adj[x].push_back(y);
		adj[y].push_back(x);
		m--;
	}
	
	dfs(1, 0);
	g << nrComp << endl;
	
	for (i = 1; i <= nrComp; i++) {	
		for (auto it = sol[i].begin(); it != sol[i].end(); it++) {
			g << *it << ' ';
		}
	
		g << '\n';
	}	
	
	return 0;	
}