Pagini recente » Cod sursa (job #3168422) | Cod sursa (job #1088291) | Cod sursa (job #6457) | Cod sursa (job #1378122) | Cod sursa (job #2567177)
#include <bits/stdc++.h>
#define lsb(x) (x & (-x))
#define ll long long
#define ull unsigned long long
#define uint unsigned int
using namespace std;
vector <vector <int>> g, comps;
vector <int> low, lvl;
stack <int> stk;
void dfs(int nod, int par) {
lvl[nod] = lvl[par] + 1;
low[nod] = lvl[nod];
stk.push(nod);
for(auto it : g[nod]) {
if(lvl[it] == 0) {
dfs(it, nod);
if(low[it] >= lvl[nod]) {
comps.push_back(vector <int>());
while(stk.top() != it) {
comps.back().push_back(stk.top());
stk.pop();
}
stk.pop();
comps.back().push_back(it);
comps.back().push_back(nod);
}
low[nod] = min(low[nod], low[it]);
}
else if(it != par) {
low[nod] = min(low[nod], lvl[it]);
}
}
}
int main() {
#ifdef HOME
ifstream cin("A.in");
ofstream cout("A.out");
#endif
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int i, n, m;
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
cin >> n >> m;
g.resize(n + 1);
for(i = 1; i <= m; i++) {
int x, y; cin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
low.resize(n + 1), lvl.resize(n + 1);
for(i = 1; i <= n; i++) {
if(lvl[i] == 0) {
dfs(i, 0);
}
}
cout << comps.size() << "\n";
for(auto &arr : comps) {
for(auto it : arr) {
cout << it << " ";
}
cout << "\n";
}
return 0;
}