Cod sursa(job #2610756)

Utilizator Mihai145Oprea Mihai Adrian Mihai145 Data 5 mai 2020 16:54:18
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.27 kb
#include <fstream>
#include <vector>
#include <stack>

using namespace std;

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

const int NMAX = 1e5;

int N, M;
vector <int> g[NMAX + 2];

bool seen[NMAX + 2];
int timee[NMAX + 2], lowTime[NMAX + 2];

stack <int> st;

int nrBix;
vector <int> bix[NMAX + 2];

void dfs(int node, int dady)
{
	timee[node] = lowTime[node] = timee[dady] + 1;
	st.push(node);

	for(auto it : g[node])
		if(it == dady) continue;
		else
		{
			if(timee[it])
			{
				lowTime[node] = min(lowTime[node], timee[it]);
				continue;
			}

			dfs(it, node);
			lowTime[node] = min(lowTime[node], lowTime[it]);

			if(timee[node] <= lowTime[it]) ///node punct de articulatie
			{
				++nrBix;

				int k;
				do
				{
					k = st.top(); st.pop();
					bix[nrBix].push_back(k);
				}
				while(k != it);
				
				bix[nrBix].push_back(node);
			}
		}
}

int main()
{
	cin >> N >> M;

	for(int i = 1; i <= M; i++)
		{
			int x, y;
			cin >> x >> y;
			g[x].push_back(y);
			g[y].push_back(x);
		}

	for(int i = 1; i <= N; i++)
		if(!timee[i]) dfs(i, 0);

	cout << nrBix << '\n';
	for(int i = 1; i <= nrBix; i++)
		{
			for(auto it : bix[i])
				cout << it << ' ';
			cout << '\n';
		}

	return 0;
}