Pagini recente » Cod sursa (job #1112008) | Cod sursa (job #3212582) | Cod sursa (job #3264372) | Cod sursa (job #1186567) | Cod sursa (job #3005018)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int MAXN = 1e5;
struct Edge {
int u, v;
};
int N, M;
int cnt, compCount;
int desc[MAXN + 1], low[MAXN + 1];
int fr[MAXN + 1];
bool visited[MAXN + 1];
vector<int> G[MAXN + 1];
vector<int> compNodes[MAXN + 1];
int top;
Edge edges[2 * MAXN + 1];
// Vom vrea sa tinem o "stiva" care sa retina muchiile parcurse (in ordine)
void removeEdges(Edge e) {
while (top > 0 && !(edges[top - 1].u == e.u && edges[top - 1].v == e.v)) {
compNodes[compCount].push_back(edges[top - 1].u);
compNodes[compCount].push_back(edges[top - 1].v);
top--;
}
compNodes[compCount].push_back(edges[top - 1].u);
compNodes[compCount].push_back(edges[top - 1].v);
top--;
compCount++;
}
void dfs(int u) {
visited[u] = true;
desc[u] = low[u] = cnt++;
for (int v : G[u]) {
if (!visited[v]) {
Edge e;
e.u = u;
e.v = v;
edges[top++] = e;
dfs(v);
low[u] = min(low[u], low[v]);
if (desc[u] <= low[v]) {
// Avem un punct de articulatie
// Stim ca pe muchai u -> v ne-am dus in jos si nu ne-am putut intoarce undeva mai sus decat u
// Atunci, vrem sa scoatem din lista de muchii toate muchiile parcurse dupa muchia u -> v
// Atunci stim ca toate nodurile care apartin muchiilor scoate sunt intr-o comp conexa.
removeEdges(e);
}
} else {
low[u] = min(low[u], desc[v]);
}
}
}
int main() {
in >> N >> M;
for (int i = 0; i < M; i++) {
int u, v; in >> u >> v;
G[u].push_back(v);
G[v].push_back(u);
}
for (int i = 1; i <= N; i++) {
if (!visited[i]) {
dfs(i);
}
}
out << compCount << "\n";
for (int i = 0; i < compCount; i++) {
vector<int> nodeList;
for (int node : compNodes[i]) {
fr[node]++;
if (fr[node] == 1) {
nodeList.push_back(node);
}
}
for (int node : compNodes[i]) {
fr[node]--;
}
for (int node : nodeList) {
out << node << " ";
}
out << "\n";
}
return 0;
}