Cod sursa(job #2404276)

Utilizator Petrisor98Anghel Ionut Petrisor Petrisor98 Data 12 aprilie 2019 14:41:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.25 kb
#include<fstream>
	
#include<vector>
	
#define nmax 100100
	
using namespace std;
	
vector <int> v[nmax],sol[2*nmax];
	
vector <pair <int, int> > s;
	
int acc[nmax],niv[nmax],u[nmax];
	
int nr;
	
void dfs(int nod, int pre)
	
{
	
	acc[nod]=niv[nod]=niv[pre]+1;
	
	u[nod]=1;
	
	vector<int> :: iterator fiu;
	
	for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
	
		if(*fiu!=pre)
	
			if(!u[*fiu])
	
			{
	
				s.push_back(make_pair(nod,*fiu));
	
				dfs(*fiu,nod);
	
				if(acc[nod]>acc[*fiu])
	
					acc[nod]=acc[*fiu];
	
				if(acc[*fiu]>=niv[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
	
				if(acc[nod]>niv[*fiu])
	
					acc[nod]=niv[*fiu];
	
}		
	
int main()
	
{
	
	int m,x,y,i,n;
	
	ifstream read("biconex.in");
	
	ofstream write("biconex.out");
	
	read>>n>>m;
	
	while(m--)
	
	{
	
		read>>x>>y;
	
		v[x].push_back(y);
	
		v[y].push_back(x);
	
	}
	
	dfs(1,0);
	
	write<<nr<<'\n';
	
	vector<int> :: iterator fiu;
	
	for(i=1;i<=nr;i++)
	
	{
	
		for(fiu=sol[i].begin();fiu!=sol[i].end();fiu++)
	
			write<<*fiu<<' ';
	
		write<<'\n';
	
	}
	
	return 0;
	
}