Pagini recente » Cod sursa (job #2697151) | Cod sursa (job #1932524) | Cod sursa (job #2657646) | Cod sursa (job #2596460) | Cod sursa (job #2886879)
#include <fstream>
#include <vector>
#include <stack>
std::ifstream fin("biconex.in");
std::ofstream fout("biconex.out");
int const NMAX = 100000;
std::vector<int> G[NMAX + 5];
int p[NMAX + 5];
int depth[NMAX + 5];
int low[NMAX + 5];
std::vector<std::vector<int>> comp;
int compCount = 0;
std::stack<int> st;
void dfs (int nod, int currDepth) {
depth[nod] = currDepth;
low[nod] = depth[nod];
st.push(nod);
for (auto x : G[nod]) {
if (depth[x] == 0) {
p[x] = nod;
dfs(x, currDepth + 1);
if (low[x] >= depth[nod]) {
comp.push_back({}); compCount++;
int top;
do {
top = st.top();
st.pop();
comp[compCount - 1].push_back(top);
} while (top != nod);
st.push(nod);
}
low[nod] = std::min(low[nod], low[x]);
} else if (x != p[nod])
low[nod] = std::min(low[nod], low[x]);
}
}
int main() {
int n, m;
fin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
p[1] = 0;
dfs (1, 1);
fout << compCount << "\n";
for (int i = 0; i < compCount; i++) {
int size = comp[i].size();
for (int j = 0; j < size; j++)
fout << comp[i][j] << " ";
fout << "\n";
}
return 0;
}