Cod sursa(job #2274491)

Utilizator shantih1Alex S Hill shantih1 Data 1 noiembrie 2018 21:32:05
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.93 kb
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
#define nmx 100005

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

int n,m,i,j,nv,nz;
int h[nmx],mn[nmx],v[nmx];
vector<int> ad[nmx],rz[nmx];

void cbic(int nd,int l)
{
	h[nd]=mn[nd]=l;
	v[++nv]=nd;
	for(int i: ad[nd])
	{
		if(h[i]==0)
		{
			if(v[nv]!=nd)	v[++nv]=nd;
			cbic(i,l+1);
			if(mn[i]>=l)
			{
				nz++;
				do
				{
					rz[nz].push_back(v[nv]);
					nv--;
				} while(v[nv]!=nd);
				rz[nz].push_back(v[nv]);
			}
			mn[nd]=min(mn[nd], mn[i]);
		}
		mn[nd]=min(mn[nd], h[i]);
	}
}
int main() {
	
	fin>>n>>m;
	for(i=1;i<=m;i++)
	{
		fin>>j>>nv;
		ad[j].push_back(nv);
		ad[nv].push_back(j);
	}
	nv=0;
	cbic(1,1);
	
	fout<<nz<<"\n";
	for(i=1;i<=nz;i++)
	{
		sort(rz[i].begin(),rz[i].end());
		nv=(int)rz[i].size();
		fout<<rz[i][0]<<" ";
		for(int j=1;j<nv;j++)
			if(rz[i][j]!=rz[i][j-1])
				fout<<rz[i][j]<<" ";
		fout<<"\n";
	}
}