Pagini recente » Cod sursa (job #1157734) | Cod sursa (job #2548713) | Cod sursa (job #2371832) | Cod sursa (job #2913776) | Cod sursa (job #2651878)
#include <fstream>
#include <vector>
#include <queue>
#include <stack>
#include <string.h>
#define N 100005
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
int n, m;
bool vizitat[N];
int lowestLevel[N], level[N];
vector<vector<int> > graf(N), solutie;
stack<int> stiva;
struct grafNod{
int x, tata;
};
queue<grafNod> coada;
void adauga(grafNod nod){
vector<int> crt;
while(stiva.top() != nod.x){
crt.push_back(stiva.top());
stiva.pop();
}
stiva.pop();
crt.push_back(nod.x);
crt.push_back(nod.tata);
solutie.push_back(crt);
}
void dfs(){
grafNod nod = coada.front();
coada.pop();
vizitat[nod.x] = true;
for(size_t i = 0; i < graf[nod.x].size(); ++i){
if(graf[nod.x][i] == nod.tata) continue;
if(vizitat[graf[nod.x][i]]) lowestLevel[nod.x] = min(lowestLevel[nod.x], level[graf[nod.x][i]]);
else{
stiva.push(graf[nod.x][i]);
level[graf[nod.x][i]] = level[nod.x] + 1;
grafNod nod2;
nod2.x = graf[nod.x][i];
nod2.tata = nod.x;
coada.push(nod2);
dfs();
lowestLevel[nod.x] = min(lowestLevel[nod.x], lowestLevel[graf[nod.x][i]]);
if(level[nod.x] <= lowestLevel[graf[nod.x][i]])
adauga(nod2);
}
}
}
int main()
{
in>>n>>m;
while(m--){
int x, y;
in>>x>>y;
graf[x].push_back(y);
graf[y].push_back(x);
}
memset(lowestLevel, 0x3f, sizeof lowestLevel);
for(int i = 1; i <= n; ++i)
if(!vizitat[i]){
grafNod nod;
nod.x = i; nod.tata = 0;
coada.push(nod);
dfs();
}
out<<solutie.size()<<'\n';
for(size_t i = 0; i < solutie.size(); ++i){
for(size_t j = 0; j < solutie[i].size(); ++j)
out<<solutie[i][j]<<" ";
out<<'\n';
}
in.close();
out.close();
return 0;
}