Pagini recente » Cod sursa (job #2904485) | Cod sursa (job #2904574) | Cod sursa (job #214512) | Cod sursa (job #2172069) | Cod sursa (job #2372589)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <utility>
#include <cmath>
#include <string>
#include <cstring>
#include <set>
#include <queue>
#include <map>
#include <stack>
#include <iomanip>
#define ll long long
#define lsb(x) (x & -x)
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;
stk.pop();
aux.push_back(a);
aux.push_back(b);
} while(x != a && y != b);
ans.push_back(aux);
}
void dfs(int node, int dad, vector<bool> &visited, vector<int> &dp, vector<int> &h, vector<vector<int>> &g) {
visited[node] = 1;
dp[node] = h[node];
for(auto it : g[node]) {
if(it == dad)
continue;
if(!visited[it]) {
stk.push({node, it});
h[it] = h[node] + 1;
dfs(it, node, visited, dp, h, g);
dp[node] = min(dp[node], dp[it]);
if(dp[it] >= h[node]) {
getcomponent(node, it);
}
} else
dp[node] = min(dp[node], h[it]);
}
}
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<bool> visited(n + 1, 0);
vector<int> dp(n + 1, 0);
vector<int> h(n + 1, 0);
h[1] = 1;
dfs(1, 0, visited, dp, h, g);
out << ans.size() << "\n";
for(auto &it : ans) {
sort(it.begin(), it.end());
int last = 0;
for(auto it2 : it) {
if(it2 != last)
out << it2 << " ";
last = it2;
}
out << "\n";
}
return 0;
}