Cod sursa(job #3002018)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 14 martie 2023 11:30:28
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 1.57 kb
#include <cstdio>
#include <cmath>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <map>
#include <cstring>
#include <algorithm>

#define NMAX 100003

using namespace std;

FILE* fin, * fout;

int n, m,k,nrc;
bool viz[NMAX];
int niv[NMAX], nMin[NMAX];
int stiv[NMAX];
vector<int>graf[NMAX];
vector<int>comp[NMAX];

void dfs(int nod, int prec, int nivel)
{
	viz[nod] = true;
	niv[nod] = nivel + 1;
	nMin[nod] = niv[nod];
	stiv[++k] = nod;
	for (int i = 0; i < graf[nod].size(); i++)
	{
		int nd = graf[nod][i];
		if (nd != prec )
		{
			if (!viz[nd])
			{
				dfs(nd, nod,nivel+1);
				nMin[nod] = min(nMin[nod], nMin[nd]);
				if (nMin[nd] >= niv[nod])
				{
					nrc++;
					int aux;
					do {
						aux = stiv[k];
						comp[nrc].push_back(aux);
						k--;
					} while (k > 0 && aux != nd);
					comp[nrc].push_back(nod);
				}
			}
			else {
				nMin[nod] = min(nMin[nod], niv[nd]);

			}
		}
	}
	
}

int main()
{
	fin = fopen("biconex.in", "r");
	fout = fopen("biconex.out", "w");
	
	fscanf(fin, "%d %d", &n, &m);
	for (int i = 1; i <= m; i++)
	{
		int x, y;
		fscanf(fin, "%d %d", &x, &y);
		graf[x].push_back(y);
		graf[y].push_back(x);
	}
	memset(niv, INT_MAX, sizeof((niv)));
	memset(nMin, INT_MAX, sizeof((nMin)));

	dfs(1, 0, 0);
	fprintf(fout, "%d\n", nrc);
	for (int i = 1; i <= nrc; i++)
	{
		for (int j = 0; j < comp[i].size(); j++)
		{
			fprintf(fout, "%d ", comp[i][j]);
		}
		fprintf(fout, "\n");
	}
	return 0;
}