Pagini recente » Cod sursa (job #1349498) | Cod sursa (job #458191) | Cod sursa (job #564806) | Cod sursa (job #619273) | Cod sursa (job #3264575)
#include <fstream>
#include <vector>
#include <unordered_set>
using namespace std;
ifstream cin("biconex.in");
ofstream cout("biconex.out");
const int NMAX = 1e5;
int n, m, t, ind_edges, ind_bcc;
vector<int> g[NMAX + 1];
int low[NMAX + 1];
int dfs_time[NMAX + 1];
pair<int, int> edges[NMAX + 1];
unordered_set<int> bcc[NMAX + 1];
void GetBCC(pair<int, int> root_edge) {
ind_bcc++;
while (edges[ind_edges] != root_edge) {
bcc[ind_bcc].insert(edges[ind_edges].first);
bcc[ind_bcc].insert(edges[ind_edges].second);
ind_edges--;
}
bcc[ind_bcc].insert(edges[ind_edges].first);
bcc[ind_bcc].insert(edges[ind_edges].second);
ind_edges--;
}
void DFS(int node, int dad = 0) {
dfs_time[node] = low[node] = ++t;
for (int next_node : g[node]) {
if (next_node != dad && dfs_time[next_node] < dfs_time[node]) {
// Take this edge if it doesn't point to dad and it has not been added to the stack
// 1. dfs_time[next_node] = 0, then its a forward edge
// 2. dfs_time[next_node] != 0, then its a back edge and we choose to add it in this orientation
// Making it to be added only once in the stack.
edges[++ind_edges] = { node, next_node };
}
if (!low[next_node]) {
DFS(next_node, node);
//edges[++ind_edge] = { node, next_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) {
low[node] = min(low[node], dfs_time[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);
}
for (int i = 1; i <= n; i++) {
if (!low[i]) {
DFS(i);
}
}
cout << ind_bcc << '\n';
for (int i = 1; i <= ind_bcc; i++, cout << '\n') {
for (int x : bcc[i]) {
cout << x << ' ';
}
}
return 0;
}