Pagini recente » Istoria paginii utilizator/laviniasuciu | Cod sursa (job #3245435) | Cod sursa (job #3292141) | Cod sursa (job #3289041) | Cod sursa (job #1394088)
#include <bits/stdc++.h>
using namespace std;
class Graph {
public:
Graph(int _N) : N(_N) {
edges.assign(N, vector<int>());
dfn.assign(N, -1);
low_link.assign(N, -1);
}
void addEdge(int x, int y) {
edges[x].push_back(y);
edges[y].push_back(x);
}
vector <vector <int> > solve() {
for (int i = 0; i < N; ++i) {
if (dfn[i] == -1) {
tarjan(i, 1, -1);
}
}
return components;
}
private:
vector <vector <int> > edges, components;
vector <int> dfn, low_link;
stack <pair <int, int> > st;
int N;
void pop_stack(pair <int, int> cur_edge) {
vector <int> partial;
while(!st.empty()) {
int y = st.top().second;
st.pop();
partial.push_back(y);
if (y == cur_edge.second) {
break;
}
}
partial.push_back(cur_edge.first);
components.push_back(partial);
}
void tarjan(int node, int father, int when) {
dfn[node] = low_link[node] = when;
for (auto neigh: edges[node]) {
if (dfn[neigh] == -1) {
st.push(make_pair(node, neigh));
tarjan(neigh, node, when + 1);
low_link[node] = min(low_link[node], low_link[neigh]);
if (low_link[neigh] >= dfn[node]) {
cerr << "articulatie " << node << "\n";
pop_stack(make_pair(node, neigh));
}
} else if (neigh != father) {
low_link[node] = min(low_link[node], dfn[neigh]);
}
}
}
};
int main() {
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int N, M; cin >> N >> M;
Graph G(N);
while(M--) {
int x, y; cin >> x >> y;
x--; y--;
G.addEdge(x, y);
}
vector <vector <int> > components = G.solve();
cout << components.size() << "\n";
for (auto it: components) {
for (auto node: it) {
cout << node + 1 << " ";
}
cout << "\n";
}
return 0;
}