Pagini recente » Cod sursa (job #2855374) | Cod sursa (job #880650) | Cod sursa (job #554730) | Cod sursa (job #2225047) | Cod sursa (job #2176176)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#include <algorithm>
#define maxN 100005
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, t, low[maxN], timp[maxN], parent[maxN], art[maxN];
vector <int> G[maxN];
vector <vector <int> > C;
stack <pair <int, int> > st;
void add (int x, int y) {
vector <int> comp;
int tx = 0, ty = 0;
while (tx != x or ty != y) {
tx = st.top().first , ty = st.top().second;
st.pop();
comp.push_back(tx), comp.push_back(ty);
}
C.push_back(comp);
}
void dfs (int nod) {
int childs = 0;
low[nod] = timp[nod] = ++t;
int size = G[nod].size();
for (int i = 0; i < size; ++i) {
int u = G[nod][i];
if (timp[u] == 0) {
childs++;
parent[u] = nod;
st.push({nod, u});
dfs(u);
low[nod] = min(low[nod], low[u]);
/*if (parent[nod] == 0 and childs > 1) {
art[nod]++;
add(nod, u);
}*/
if (low[u] >= timp[nod]) {
art[nod]++;
add(nod, u);
}
}
else {
low[nod] = min(low[nod], timp[u]);
}
}
}
int main () {
fin >> n >> m;
int x, y;
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
/*for (int i = 1; i <= n; ++i) {
if (art[i])
fout << i << " ";
}*/
fout << C.size() << '\n';
int size = C.size();
for (int i = 0; i < size; ++i) {
sort(C[i].begin(), C[i].end());
C[i].erase(unique(C[i].begin(), C[i].end()), C[i].end());
int size1 = C[i].size();
for (int j = 0; j < size1; ++j) {
fout << C[i][j] << " ";
}
fout << '\n';
}
}