Pagini recente » Cod sursa (job #1996803) | Cod sursa (job #1788589) | Cod sursa (job #1233080) | Cod sursa (job #2058836) | Cod sursa (job #3004983)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
const int DIM = 100010;
int n, m, x, y;
int biconCompCnt = 0;
int level[DIM], low[DIM];
vector<int> l[DIM], biconComp[DIM];
stack<int> st;
bool visited[DIM];
void dfs(int node, int father, int lvl) {
visited[node] = true;
level[node] = low[node] = lvl;
st.push(node);
for (auto adjNode : l[node]) {
if (adjNode == father) continue;
if (!visited[adjNode]) {
dfs(adjNode, node, lvl + 1);
low[node] = min(low[node], low[adjNode]);
if (level[node] <= low[adjNode]) {
++biconCompCnt;
while (st.top() != adjNode) {
biconComp[biconCompCnt].push_back(st.top());
st.pop();
}
biconComp[biconCompCnt].push_back(adjNode);
st.pop();
biconComp[biconCompCnt].push_back(node);
}
} else {
low[node] = min(low[node], level[adjNode]);
}
}
}
int main() {
fin >> n >> m;
for (int i = 1; i <= m; i++) {
fin >> x >> y;
l[x].push_back(y);
l[y].push_back(x);
}
dfs(1, 0, 0);
fout << biconCompCnt << '\n';
for (int i = 1; i <= biconCompCnt; i++) {
for (auto node : biconComp[i])
fout << node << ' ';
fout << '\n';
}
return 0;
}