Pagini recente » Cod sursa (job #985424) | Cod sursa (job #1176135) | Cod sursa (job #3286988) | Cod sursa (job #117415) | Cod sursa (job #2672033)
#include <bits/stdc++.h>
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
int viz[100002];
int low[100002];
int ind;
bool s[100002], c[100002];
vector <int> g[100002];
vector <int> sol[100002];
stack <int> st;
void DFS(int node, int &niv) {
niv = niv + 1;
viz[node] = niv;
low[node] = niv;
s[node] = 1;
st.push(node);
for (int i = 0; i < g[node].size(); ++i) {
int nou = g[node][i];
if (!viz[nou]) {
DFS(nou, niv);
low[node] = min(low[node], low[nou]);
if (viz[node] <= low[nou]) {
ind++;
while(st.top()!= nou) {
s[st.top()] = 0;
sol[ind].push_back(st.top());
st.pop();
}
sol[ind].push_back(nou);
sol[ind].push_back(node);
s[nou] = 0;
st.pop();
}
}
else if (s[nou])
low[node] = min(low[node], viz[nou]);
}
}
int main() {
int n, m, x, y;
fin >> n >> m;
for (int i = 1; i <= m; ++i) {
fin >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
int niv = 0;
DFS(1, niv);
fout << ind << '\n';
for (int i = 1; i <= ind; ++i) {
for (int j = 0; j < sol[i].size(); ++j)
fout << sol[i][j] << ' ';
fout << '\n';
}
return 0;
}