Pagini recente » Cod sursa (job #1328662) | Cod sursa (job #783183) | Cod sursa (job #1157006) | Cod sursa (job #2322767) | Cod sursa (job #3288771)
#include <fstream>
#include <vector>
#include <unordered_set>
#include <algorithm>
using namespace std;
const int NMAX = 1e5;
const int MMAX = 2e5;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, ind_bcc, ind_edges, t;
vector<int> g[NMAX + 1];
vector<int> bcc[NMAX + 1];
pair<int, int> edges[MMAX + 1];
int dfs_time[NMAX + 1];
int low[NMAX + 1];
void GetBCC(pair<int, int> root_edge) {
ind_bcc++;
while(root_edge != edges[ind_edges]) {
bcc[ind_bcc].push_back(edges[ind_edges].first);
bcc[ind_bcc].push_back(edges[ind_edges].second);
ind_edges--;
}
bcc[ind_bcc].push_back(edges[ind_edges].first);
bcc[ind_bcc].push_back(edges[ind_edges].second);
ind_edges--;
sort(bcc[ind_bcc].begin(), bcc[ind_bcc].end());
bcc[ind_bcc].erase(unique(bcc[ind_bcc].begin(), bcc[ind_bcc].end()), bcc[ind_bcc].end());
}
void DFS(int node, int dad = 0) {
dfs_time[node] = low[node] = ++t;
for(int next_node : g[node]) {
if(!dfs_time[next_node]) {
edges[++ind_edges] = {node, next_node};
DFS(next_node, node);
low[node] = min(low[node], low[next_node]);
if(low[next_node] >= dfs_time[node]) {
GetBCC({node, next_node});
}
}
else if(next_node != dad && dfs_time[node] > dfs_time[next_node]) {
low[node] = min(low[node], dfs_time[next_node]);
edges[++ind_edges] = {node, next_node};
}
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int a, b;
cin >> a >> b;
g[a].push_back(b);
g[b].push_back(a);
}
DFS(1);
cout << ind_bcc << '\n';
for(int i = 1; i <= ind_bcc; i++) {
for(int x : bcc[i]) {
cout << x << ' ';
}
cout << '\n';
}
return 0;
}