Cod sursa(job #2147031)

Utilizator DeleDelegeanu Alexandru Dele Data 28 februarie 2018 13:22:08
Problema Componente biconexe Scor 90
Compilator cpp Status done
Runda Arhiva educationala Marime 1.21 kb
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> a[MAX];
vector< vector<int> > sol;
stack<int> st;
bool viz[MAX];
int nro[MAX],low[MAX];
int nrb,root;
int n,m,x,y;
void biconex(int x,int t){
	viz[x]=true;
	nro[x]=low[x]=nro[t]+1;
	st.push(x);

	for(int i=0 ; i<a[x].size() ; ++i)
    {
        int it=a[x][i];
		if(it==t)
			continue;
		if(viz[it])
		{
			low[x]=min(low[x],nro[it]);
			continue;
		}

		biconex(it, x);
		low[x]=min(low[x],low[it]);

		if(nro[x]<=low[it])
        {
			sol.push_back(vector<int>(0));
			int z;
			do{
				z=st.top();
				st.pop();
				sol[nrb].push_back(z);
			}while(z!=it);
			sol[nrb].push_back(x);
            ++nrb;
		}
	}
}
int main()
{
	f>>n>>m;
	for(int i=1 ; i<=m; ++i)
    {
		f>>x>>y;
		a[x].push_back(y);
		a[y].push_back(x);
	}

	for(int i=1 ; i<=n ; ++i)
		if (!viz[i])
        {
            root=i;
            biconex(i,0);
        }

    g<<nrb<<'\n';
    for(int i=0 ; i<sol.size() ; ++i)
    {
        for(int j=0 ; j<sol[i].size() ; ++j)
            g<<sol[i][j]<<" ";
        g<<'\n';
    }
	return 0;

}