Pagini recente » Cod sursa (job #2541946) | Cod sursa (job #2531756) | Cod sursa (job #3294869) | Cod sursa (job #33438) | Cod sursa (job #3299866)
#include <fstream>
#include <stack>
#include <vector>
using namespace std;
const int NMAX = 100002;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
vector <vector <int>> v;
int niv[NMAX]; ///dist de la nod la radacina
int h[NMAX]; ///cel mai de sus nod pe care il poate accesa DIN SUBARB, prin max o singura muchie de intoarcere
bool f[NMAX];
stack <int> s; ///pt comp
vector <vector <int>> bicon;
void dfs(int start, int tata) {
//cout << "DFS " << start << '\n';
f[start] = 1;
s.push(start);
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[nod];
dfs(nod, start);
h[start] = min(h[start], h[nod]);
if(h[nod] >= niv[start]) { ///punct de art, NU se poate ajunge mai sus, it's over
//cout << "comp " << nod << " " << start << '\n';
bicon.push_back(vector <int>());
while(!s.empty() && s.top() != nod) { ///pana la el
bicon.back().push_back(s.top());
s.pop();
}
bicon.back().push_back(start);
bicon.back().push_back(nod);
s.pop();
/*for(auto var : bicon.back())
cout << var << " ";
cout << '\n';*/
}
}
//cout << "FINAL " << start << " si " << niv[start] << " " << h[start] << '\n';
}
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] = 1;
h[1] = 1;
dfs(1, 0);
/*for(int i = 1; i <= n; i++)
cout << niv[i] << " ";
cout << '\n';
for(int i = 1; i <= n; i++)
cout << h[i] << " ";*/
cout << bicon.size() << '\n';
for(int i = 0; i < bicon.size(); i++) {
for(auto x : bicon[i])
cout << x << " ";
cout << '\n';
}
return 0;
}