Cod sursa(job #797250)

Utilizator mihaibogdan10Mihai Bogdan mihaibogdan10 Data 13 octombrie 2012 17:36:07
Problema Componente biconexe Scor 0
Compilator cpp Status done
Runda Arhiva educationala Marime 1.5 kb
#include<cstdio>
#include<vector>
#include<stack>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in"); ofstream fout("biconex.out");

int n, m, index, lowlink[100001], tata[100001], entry_time[100001];
vector <int> G[100001];
vector <vector <int> > sol;
stack <int> bcStack;

void DFS(int nod){
	int i, adj;
	
	bcStack.push(nod);
	lowlink[nod] = entry_time[nod] = ++index;
	vector <int> newbc;
	
	for (i = 0; i < (int)G[nod].size(); i++){
		adj = G[nod][i];
		
		if (!entry_time[adj]) {
			tata[adj] = nod;
			DFS(adj);
			// la intoarcerea din recursie, lowlink[tata] = min lowlink[fii]
			lowlink[nod] = min (lowlink[nod], lowlink[adj]);
		}
		// am intalnit o muchie de intoarcere
		else if (tata[nod] != adj) 
			lowlink[nod] = min (lowlink[nod], lowlink[adj]);		
	}
	
	if (lowlink[nod] == entry_time[nod]){
		do	{
			adj = bcStack.top(), bcStack.pop();
			newbc.push_back(adj);
		}
		while (nod != adj);		
		if (newbc.size() > 1)sol.push_back(newbc);
		//daca este cazul, adauga comp biconexa formata din nodul de articulatie si tatal lui
		if (tata[nod]){
			newbc.clear();
			newbc.push_back(nod), newbc.push_back(tata[nod]);
			sol.push_back(newbc);
		}
	}
}

int main(){
	int i, j, x, y;
	fin >> n >> m;
	for (i = 0; i <= m; i++){
		fin >> x >> y;
		G[x].push_back(y);
		G[y].push_back(x);
	}
	
	for (i = 1; i <= n ;i++)
		if (!entry_time[i]) DFS(i);
	
	fout << sol.size() << "\n";
	for (i = 0; i < (int)sol.size(); i++){
		for (j = 0; j < (int)sol[i].size(); j++)
			fout << sol[i][j] << " ";
		fout << "\n";
	}
}