Pagini recente » Cod sursa (job #1199982) | Cod sursa (job #824494) | Cod sursa (job #118726) | Cod sursa (job #3329189) | Cod sursa (job #3309461)
#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 = 0, int v = 0) {
if (!st.empty()) {
Edge crt;
set<int> comp;
do {
crt = st.top(); st.pop();
comp.insert(crt.u);
comp.insert(crt.v);
} while (!st.empty() && (crt.u != u || crt.v != v) && (crt.u != v && crt.v != u));
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_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;
}