Pagini recente » Cod sursa (job #3355606) | Cod sursa (job #2926254) | Cod sursa (job #1721043) | Cod sursa (job #3305187) | Cod sursa (job #3303494)
#include <fstream>
#include <bitset>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100002;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector <vector <int>> v, bicon;
stack <int> s;
int niv[NMAX]; ///depth (basically dist fata de rad)
int h[NMAX];
bitset <NMAX> f;
void dfs(int start, int tata) {
s.push(start);
f[start] = 1;
for(auto nod : v[start]) {
if(nod == tata)
continue;
if(f[nod]) { ///muchie de intoarcere
h[start] = min(h[start], niv[nod]);
continue;
}
niv[nod] = niv[start] + 1;
h[nod] = niv[start] + 1;
dfs(nod, start);
h[start] = min(h[start], h[nod]);
if(h[nod] >= niv[start]) { ///NU se poate ajunge mai sus, gg well played
bicon.push_back(vector<int>());
while(!s.empty() && s.top() != nod) {
bicon.back().push_back(s.top());
s.pop();
}
bicon.back().push_back(nod);
bicon.back().push_back(start);
s.pop();
}
}
}
int main()
{
int n, m;
cin >> n >> m;
v.resize(n + 1);
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
niv[1] = 0, h[1] = 0;
dfs(1, 0);
cout << bicon.size() << '\n';
for(int i = 0; i < bicon.size(); i++) {
for(auto x : bicon[i])
cout << x << " ";
cout << '\n';
}
return 0;
}