Pagini recente » Cod sursa (job #3347316) | Cod sursa (job #3342368) | Cod sursa (job #3342547) | Cod sursa (job #3352157) | Cod sursa (job #3309463)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int MAX_N = 100000;
const int INF = MAX_N + 1;
vector<vector<int>> adj;
vector<set<int>> bicomp;
int dfn[MAX_N + 1], low[MAX_N + 1];
int parent[MAX_N + 1];
bool vis[MAX_N + 1];
int n, m, num;
struct Edge {
int u, v;
};
stack<Edge> st;
void read() {
fin >> n >> m;
adj = vector<vector<int>>(n + 1);
int x, y;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
}
void init() {
for (int i = 1; i <= n; i++) {
dfn[i] = parent[i] = -1;
low[i] = INF; vis[i] = 0;
}
}
void process_comp(int u, int v) {
if (!st.empty()) {
set<int> comp;
while ((st.top().u != u || st.top().v != v) &&
(st.top().u != v || st.top().v != u)) {
comp.insert(st.top().u);
comp.insert(st.top().v);
st.pop();
}
comp.insert(st.top().u);
comp.insert(st.top().v);
st.pop();
bicomp.push_back(comp);
}
}
void process_rem_comp() {
if (!st.empty()) {
set<int> comp;
while (!st.empty()) {
comp.insert(st.top().u);
comp.insert(st.top().v);
st.pop();
}
bicomp.push_back(comp);
}
}
void dfs(int vertex) {
dfn[vertex] = low[vertex] = ++num;
vis[vertex] = 1;
int child = 0;
for (int x : adj[vertex]) {
if (!vis[x]) {
st.push({vertex, x});
parent[x] = vertex;
child++;
dfs(x);
low[vertex] = min(low[vertex], low[x]);
if (parent[vertex] == -1 && child >= 2)
process_comp(vertex, x);
if (parent[vertex] != -1 && low[x] >= dfn[vertex])
process_comp(vertex, x);
} else {
if (parent[vertex] != x && low[vertex] > dfn[x]) {
// [vertex, x] - muchie de intoarcere / back edge
low[vertex] = dfn[x];
st.push({vertex, x});
}
}
}
}
void biconnected_comp() {
for (int i = 1; i <= n; i++)
if (!vis[i]) {
num = 0; dfs(i);
process_rem_comp();
}
}
void print_bicomp() {
fout << (int)bicomp.size() << "\n";
for (int i = 0; i < (int)bicomp.size(); i++) {
for (int vertex : bicomp[i])
fout << vertex << " ";
fout << "\n";
}
}
int main() {
read(); init();
biconnected_comp();
print_bicomp();
fin.close();
fout.close();
return 0;
}