Pagini recente » Cod sursa (job #30656) | Cod sursa (job #1818204) | Cod sursa (job #2275762) | Cod sursa (job #1255102) | Cod sursa (job #1033034)
#include<vector>
#include<iostream>
#include<fstream>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
#define MAX_N 100000
int n, m;
vector<int> list[MAX_N];
vector<int> st[2];
bool viz[MAX_N];
vector<int> biconex[MAX_N];
int contor = -1;
void citeste(){
fin >> n >> m;
int a, b;
for(int i=1; i<=m; i++){
fin >> a >> b;
list[a].push_back(b);
list[b].push_back(a);
}
}
bool in_lista(int nod1, int nod2){ // verifica daca nodul2 se afla in lista de adiacenta a nodului1
for(size_t i=0; i< list[nod1].size(); i++){
if(list[nod1][i] == nod2) return true;
}
return false;
}
int muchie_intoarcere(int nod){ // verifica daca exista muchie de intoarcere de la nod la un alt nod in stiva
for(size_t i=0; i<st[0].size()-2; i++){
if(in_lista(nod, st[0][i])){
return i; // returneaza nivelul pe care se afala nodul ce prezinta muchia de intoarcere
}
}
return -1;
}
void afis_u2(){
int lung = st[0].size();
if(lung > 1)
if(st[1][lung-1] == 0){
contor ++;
biconex[contor].push_back(st[0][lung-2]);
biconex[contor].push_back(st[0][lung-1]);
}
st[0].pop_back();
st[1].pop_back();
}
void afis(int niv){
contor ++;
for(size_t i=niv; i<st[0].size(); i++){
biconex[contor].push_back(st[0][i]);
}
st[0].erase(st[0].begin() + niv + 1, st[0].end()-1);
st[1].erase(st[1].begin() + niv + 1, st[1].end()-1);
int lung = st[1].size();
st[1][lung-1] = 1;
}
void df(int nod){
if(!viz[nod]){
viz[nod] = 1;
st[0].push_back(nod);
st[1].push_back(0);
}
if(st[0].size() > 2){
int niv = muchie_intoarcere(nod);
if(niv > (-1) ){
afis(niv);
}
}
bool gasit = false; // daca de la nod se poate merge mai departe
int nod2 = -1;
for(size_t i=0; i<list[nod].size(); i++){
int x = list[nod][i];
if(!viz[x]) {
nod2 = x;
gasit = true;
break;
}
}
if(!gasit){
afis_u2();
int lung = st[0].size();
int nod3 = -1;
if(lung > 0){
nod3 = st[0][lung-1];
df(nod3);
}
}else{
df(nod2);
}
}
int main(){
citeste();
for(int i=1; i<=n; i++){
if(!viz[i]) df(i);
}
fout << contor + 1 << '\n';
for(int i=0; i<=contor; i++){
for(size_t j=0; j<biconex[i].size(); j++){
fout << biconex[i][j] << " ";
}
fout << '\n';
}
return 0;
}