Pagini recente » Cod sursa (job #2683010) | Cod sursa (job #575985) | Cod sursa (job #956627) | Cod sursa (job #2536435) | Cod sursa (job #2122668)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int NMAX = 100005;
vector<int> g[NMAX];
stack<int> st;
int n, m, index[NMAX], lowlink[NMAX], globalIndex = -1;
vector<vector<int>> c;
void component(int node, int parent) {
vector<int> comp;
comp.push_back(parent);
while (st.top() != node) {
comp.push_back(st.top());
st.pop();
}
comp.push_back(node);
st.pop();
c.push_back(comp);
}
void dfs(int node, int parent) {
index[node] = lowlink[node] = ++globalIndex;
for (int next : g[node]) {
if (next == parent)
continue;
if (index[next])
lowlink[node] = min(lowlink[node], index[next]);
else {
st.push(next);
dfs(next, node);
lowlink[node] = min(lowlink[node], lowlink[next]);
if (lowlink[next] >= index[node])
component(next, node);
}
}
}
void read() {
in >> n >> m;
while (m--) {
int x, y;
in >> x >> y;
g[x].push_back(y);
g[y].push_back(x);
}
}
int main() {
read();
for (int i = 1; i <= n; i++) {
st.push(i);
if (!index[i])
dfs(i, 0);
st.pop();
}
out << c.size() << '\n';
for (auto comp : c) {
for (int item : comp)
out << item << ' ';
out << '\n';
}
return 0;
}