Pagini recente » Cod sursa (job #2208524) | Cod sursa (job #1023269) | Cod sursa (job #1089285) | Cod sursa (job #138958) | Cod sursa (job #2351914)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <stack>
#include <cassert>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
stack<pair<int, int>> stk;
vector<vector<int>> ans;
void getcomponent(int x, int y) {
vector<int> aux;
int a = 0, b = 0;
do {
a = stk.top().first;
b = stk.top().second;
aux.push_back(a);
aux.push_back(b);
stk.pop();
} while(a != x || b != y);
ans.push_back(aux);
}
void dfs(int node, int dad, int x, const vector<vector<int>> &g, vector<int> &dp, vector<int> &h) {
dp[node] = h[node] = x;
for(auto it : g[node]) {
if(it == dad)
continue;
if(!h[it]) {
stk.push({node, it});
dfs(it, node, x + 1, g, dp, h);
dp[node] = min(dp[node], dp[it]);
if(h[node] <= dp[it])
getcomponent(node, it);
} else
dp[node] = min(dp[node], h[it]); /// atentie aici
}
}
int main() {
int n, m;
in >> n >> m;
vector<vector<int>> g(n + 1);
for(int i = 1; i <= m; i ++) {
int a, b;
in >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
vector<int> dp(n + 1, 0);
vector<int> h(n + 1, 0);
dfs(1, 0, 1, g, dp, h);
out << ans.size() << "\n";
for(auto &it : ans) {
sort(it.begin(), it.end());
int last = -1;
for(auto it2 : it) {
if(it2 != last)
out << it2 << " ";
last = it2;
}
out << "\n";
}
return 0;
}