Cod sursa(job #3370991)

Utilizator lvncarsteaCarstea Lavinia Ionela Gabriela lvncarstea Data 28 octombrie 2026 09:17:56
Problema Componente biconexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.21 kb
#include <bits/stdc++.h>
using namespace std;

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

const int nmax = 100001;
int noduri, muchii, x, y, nr_art, nr_comp;

vector<int> graf[nmax], grafcp[nmax];
int pct_art[nmax], elm[nmax], viz[nmax];

int niv[nmax], nma[nmax];
vector<pair<int, int>> st;
int V[nmax];

void dfs_niv(int nod, int nivel)
{
	niv[nod]=nivel;
	for(int vecin : graf[nod])
		if(niv[vecin] == 0)
			dfs_niv(vecin, nivel + 1);
}
void dfs_nma(int k, int t)
{
	V[k]=1;
	nma[k]=niv[k];
	for(int nod_vecin : graf[k])	
	{
		if(V[nod_vecin])
			{
				if(niv[nod_vecin] < niv[k])
					{
						st.push_back({nod_vecin, k});
						if(niv[nod_vecin] < nma[k])	
							nma[k]=niv[nod_vecin];
					}
			}
		else
		{
			st.push_back({k, nod_vecin});
			dfs_nma(nod_vecin, k);
			if(nma[k] > nma[nod_vecin])
				nma[k] = nma[nod_vecin];

			if(niv[k]<=nma[nod_vecin])
			{
				nr_comp++;
				vector<int> comp;
				while(!st.empty())
				{
					int nod1=st.first();
					int nod2=st.second();
					st.pop_back();
					comp.push_back(nod1);
					comp.push_back(nod2);

					if(nod1==k && nod2==nod_vecin)
                       break;
				}

				grafcp[nr_comp]=comp;
			}
		}
	}
}
int cnx()
{
	for(int i=1;i<=noduri;i++)
	{
		if(!viz[i] && !elm[i])
			return 0;
	}
	return 1;
}
void v(int nod)
{
	viz[nod]=1;
	for(int nod_vecin : graf[nod])
		if(!elm[nod_vecin] && !viz[nod_vecin])
			v(nod_vecin);
}
void read()
{
	in>>noduri>>muchii;
	for(int i=0;i<muchii;i++)
	{
		in>>x>>y;
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
}
void func()
{
	for(int i=1;i<=noduri;i++)
	{
		viz[i]=0;
		elm[i]=0;
	}
}
void noduricritice()
{
	for(int i=1;i<=noduri;i++)
		{
			if(!pct_art[i] && !pct_art[graf[i][0]])
			{
				elm[i]=1;
				v(graf[i][0]);
				if(cnx() == 0)
					{
						pct_art[i]=1;
						nr_art++;
					}
			}
			func();
		}
}
int main()
{
	read();
	noduricritice();
	for(int i=1;i<=noduri;i++)
		if(niv[i] == 0)
			dfs_niv(i,i);
	for(int i=1;i<=noduri;i++)
		if(!V[i])
			dfs_nma(i, i);

	out<<nr_comp<<'\n';

	for(int i=1;i<=nr_comp;i++)
		{
		for(int nod : grafcp[i])
			out<<nod<< " ";
		out<<'\n';
		}	

}