Cod sursa(job #2985730)

Utilizator TudosieRazvanTudosie Marius-Razvan TudosieRazvan Data 26 februarie 2023 22:57:54
Problema Componente biconexe Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 4.16 kb
#include <cstdio>
#include <cmath>
#include <climits>
#include <vector>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <bitset>
#include <unordered_map>
#include <cstring>
#include <algorithm>

#define NMAX 100003

using namespace std;


FILE* fin, * fout;

int cerinta;
int n, m, nivStiva;
bool viz[NMAX];
int componenteBiconexe;//numarul de componente biconexe
int niv[NMAX];//vector aditional pentru a transforma graful in arbore
int stiva[NMAX];//stiva asta e la fel ca la dfs doar ca aici imi pun componentele, dupa ce gasesc o componenta stiva se goleste
vector<int>graf[NMAX];

int critic[NMAX];//daca nodul i este critic
int low_level[NMAX];//aici am nivelul minim al nodurilor cu care e invecinat i venind din recursivitate(vezi desen)
vector<int>compBiconex[NMAX];//componentele biconexe
vector<pair<int, int>>muchiiCritice;//perechile de muchii critice


void dfs(int nod, int nivel, int tata) {

    //setez ca am ajuns in nodul nod
    viz[nod] = true;
    niv[nod] = nivel;
    stiva[++nivStiva] = nod;

    //setez deocamdata minimul ca fiind nivelul nodului
    low_level[nod] = niv[nod];

    //parcurg vecinii
    for (int i = 0; i < graf[nod].size(); i++) {
        int vecin = graf[nod][i];
        if (vecin == tata)
        {
            //de aici am venit
            continue;
        }

        if (!viz[vecin]) {
            //nu am vazut vecinul asta
            dfs(vecin, nivel + 1, nod);//il parcurg
            low_level[nod] = min(low_level[nod], low_level[vecin]);//iau minimul din vecin(din low)

            if (niv[nod] <= low_level[vecin]) {
                //atunci aici e o componenta biconexa
                //intru in stiva si iau cat timp am noduri in stiva
                //practic imi imaginez ca daca as scoate nodul vecin din graf, toate nodurile pana la nod formeaza o componenta biconexa
                componenteBiconexe++;
                int aux;
                do {
                    aux = stiva[nivStiva];
                    compBiconex[componenteBiconexe].push_back(stiva[nivStiva]);
                    nivStiva--;
                } while (nivStiva > 0 && aux != vecin);
                compBiconex[componenteBiconexe].push_back(nod);

                critic[nod]++;

            }

            if (niv[nod] < low_level[vecin]) {
                /// muchia este critica
                muchiiCritice.push_back({ nod, vecin });
            }


        }
        else {
            //am mai vizitat nodul asta
            //ii iau minimul si setez in low
            low_level[nod] = min(low_level[nod], niv[vecin]);
        }
    }
}

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);
	}

	for (int i = 1; i <= n; i++)
	{
		sort(graf[i].begin(), graf[i].end());//sa le am in ordine(nu e nevoie neaparat)
	}
    dfs(1, 1, 0);

    fprintf(fout, "%d\n", componenteBiconexe);
    for (int i = 1; i <= componenteBiconexe; i++) {
        sort(compBiconex[i].begin(), compBiconex[i].end());
        for (int j = 0; j < compBiconex[i].size(); j++)
        {
            fprintf(fout, "%d ", compBiconex[i][j]);
        }
        fprintf(fout, "\n");
    }
    
    

	/*if (cerinta == 2) {
		int noduriCritice = 0;
		if (critic[1] >= 2)
		{
            //caz particular-> nodul radacina e critic doar daca, prin eliminarea lui am 2 componente create
            //din cauza faptului ca e radacina
			noduriCritice = 1;
		}

		for (int i = 2; i <= n; i++) {
			if (critic[i] != 0) {
				noduriCritice++;
			}
		}

		fprintf(fout, "%d\n", noduriCritice);
		if (critic[1] >= 2)
		{
			fprintf(fout, "1 ");
		}
		for (int i = 2; i <= n; i++)
		{
			if (critic[i] != 0) {
				fprintf(fout, "%d ", i);
			}
		}
		return 0;
	}

    fprintf(fout, "%d\n", muchiiCritice.size());
    for (int i = 0; i < muchiiCritice.size(); i++)
    {
        fprintf(fout, "%d %d\n", muchiiCritice[i].first, muchiiCritice[i].second);
    }*/
	return 0;
}