Pagini recente » Cod sursa (job #2317814) | Cod sursa (job #1114446) | Cod sursa (job #961231) | Cod sursa (job #623743) | Cod sursa (job #2985730)
#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;
}