Pagini recente » Cod sursa (job #1051557) | Cod sursa (job #521792) | Cod sursa (job #2106594) | Cod sursa (job #96846) | Cod sursa (job #3204853)
#include <bits/stdc++.h>
#define NMAX 100001
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
int N, M, nivel[NMAX], nma[NMAX], k;
vector<int> vecini[NMAX];
stack<int> s;
vector< pair<int, int> > mc;
vector<int> art;
vector<int> compConex[NMAX];
bool viz[NMAX];
void dfs(int nod, int tata){
nivel[nod] = nivel[tata] + 1;
nma[nod] = nivel[nod];
viz[nod] = true;
bool pctArt = false;
s.push(nod);
for(auto vecin : vecini[nod]){
if(viz[vecin] && !(tata == vecin))
nma[nod] = min(nma[nod], nivel[vecin]);
else if(!viz[vecin]){
dfs(vecin, nod);
nma[nod] = min(nma[nod], nma[vecin]);
if(nivel[nod] <= nma[vecin] && nod != 1){
pctArt = true;
}
if(nivel[nod] < nma[vecin]){
mc.push_back(make_pair(nod, vecin));
}
if(nivel[nod] <= nma[vecin]){
k ++;
while(s.top() != vecin){
compConex[k].push_back(s.top());
s.pop();
}
compConex[k].push_back(s.top());
s.pop();
compConex[k].push_back(nod);
}
}
}
if(pctArt == true){
art.push_back(nod);
}
}
int main()
{
f >> N >> M;
for(int i = 1; i <= M; i ++){
int x, y;
f >> x >> y;
vecini[x].push_back(y);
vecini[y].push_back(x);
}
dfs(1, 0);
g << k << '\n';
for(int i = 1; i <= k; i ++){
for(auto el = compConex[i].rbegin(); el < compConex[i].rend(); el ++){
g << *el << " ";
}
g << '\n';
}
return 0;
}