Pagini recente » Cod sursa (job #2205378) | Cod sursa (job #94762) | Cod sursa (job #2835710) | Cod sursa (job #2490226) | Cod sursa (job #2090101)
#include <iostream>
#include <fstream>
#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];
bool viz[DMAX];
int stiva[DMAX], vfStiva;
int solutie[1000][1000],lg;
//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){
lg++;
solutie[lg][++solutie[lg][0]] = tata;
while(vfStiva > 0 && stiva[vfStiva]!= pctArtic){
solutie[lg][++solutie[lg][0]] = stiva[vfStiva];
vfStiva--;
}
if(vfStiva > 0) {
solutie[lg][++solutie[lg][0]] = pctArtic;
vfStiva--;
}
}
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){
low[nodAct] = min(low[parcurg -> val], nivel[parcurg -> val]);
}else{
dfs(parcurg-> val, nodAct);
low[nodAct] = min(low[parcurg -> val], nivel[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);
out << lg <<'\n';
for(int i = 1; i<= lg; i++){
for(int j = 1; j <= solutie[i][0]; j++){
out << solutie[i][j] << ' ';
}
out << '\n';
}
return 0;
}