Pagini recente » Cod sursa (job #897960) | Cod sursa (job #1402943) | Cod sursa (job #1212657) | Cod sursa (job #2869308) | Cod sursa (job #2090133)
#include <iostream>
#include <fstream>
#include <vector>
#define DMAX 100002
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
typedef struct elem{
int val;
elem *urm;
}GRAF;
GRAF *nod[DMAX];
int n, m;//date de intrare
int low[DMAX], nivel[DMAX], tata[DMAX];
int stiva[DMAX], vfStiva;
bool viz[DMAX];
vector<vector <int>> solutii;
//un graf biconex este un graf care nu are puncte de articulatie
//un punct de articulatie este un nod care, daca este scos impreuna
//cu toate muchiile incidente , graful nu mai este conex
//un punct este punct de articulatie daca nivelul cel mai de sus la care poate ajunge
//un fiu este mai mare decat nivelul nodului respectiv
void initializare(){
for(int i = 1; i <= n; i++){
nod[i] = new GRAF;
nod[i] = NULL;
}
}
void citireMuchie(){
for(int i = 1; i <= m; i++){
int x , y;
in >> x >> y;
GRAF *nodAdaug1 = new GRAF;
nodAdaug1 -> val = y;
nodAdaug1 -> urm = nod[x];
nod[x] = nodAdaug1;
GRAF *nodAdaug2 = new GRAF;
nodAdaug2 -> val = x;
nodAdaug2 -> urm = nod[y];
nod[y] = nodAdaug2;
}
}
void adaugareSolutie(int pctArtic, int tata){
vector <int> solutie;
solutie.push_back(tata);
while(vfStiva > 0 && stiva[vfStiva]!= pctArtic){
solutie.push_back(stiva[vfStiva]);
vfStiva--;
}
if(vfStiva > 0) {
solutie.push_back(pctArtic);
vfStiva--;
}
solutii.push_back(solutie);
}
void dfs(int nodAct, int tata){
stiva[++vfStiva] = nodAct;
viz[nodAct] = true;
nivel[nodAct] = nivel[tata] + 1;
low[nodAct] = nivel[nodAct];
GRAF * parcurg = new GRAF;
parcurg = nod[nodAct];
while(parcurg != NULL){
if(viz[parcurg-> val] == true){
if(parcurg -> val != tata) {
low[nodAct] = min(low[nodAct], nivel[parcurg->val]);
}
}else{
dfs(parcurg-> val, nodAct);
low[nodAct] = min(low[nodAct], low[parcurg->val]);
if(low[parcurg -> val] >= nivel[nodAct]){
adaugareSolutie( parcurg -> val, nodAct);
}
}
parcurg = parcurg -> urm;
}
}
int main() {
in >> n >> m;
initializare();
citireMuchie();
dfs(1,0);
int lgRez = solutii.size();
out << lgRez <<'\n';
for(int i = 0; i< lgRez; i++){
int lgSol = solutii[i].size();
for(int j = 0; j < lgSol; j++){
out << solutii[i][j] << ' ';
}
out << '\n';
}
return 0;
}