Pagini recente » Cod sursa (job #1623509) | Cod sursa (job #902369) | Cod sursa (job #970382) | Cod sursa (job #1362270) | Cod sursa (job #2796529)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
class Graph {
private:
int _n, _m;
vector<int> _list[100001];
public:
Graph(int nodes, int edges) : _n(nodes), _m(edges) {}
void addEdges();
vector<vector<int>> c_bic();
void biconexe(int node, int parent, stack<int> &s, vector<int> &level, vector<int> &back, vector<vector<int>> &bic);
};
void
Graph::biconexe(int node, int parent, stack<int> &s, vector<int> &level, vector<int> &back, vector<vector<int>> &bic) {
//calculez nivelurile nodurilor
level[node] = level[parent] + 1;
back[node] = level[node];
s.push(node);
//parcurg vecinii
for (int i = 0; i < _list[node].size(); i++) {
if (level[_list[node][i]]) {
if (_list[node][i] != parent)
//actualizez minimul
back[node] = min(level[_list[node][i]], back[node]);
} else {
biconexe(_list[node][i], node, s, level, back, bic); //dfs pentru biconexe
back[node] = min(back[_list[node][i]], back[node]);
if (level[node] <= back[_list[node][i]]) { //verific daca face parte din componenta biconexa
vector<int> v;
while (s.top() != _list[node][i]) {
v.push_back(s.top()); //pun in v elementele componentei biconexe
s.pop();
}
v.push_back(_list[node][i]);
s.pop();
v.push_back(node);
bic.push_back(v);
}
}
}
}
vector<vector<int>> Graph::c_bic() {
vector<vector<int>> bic;
//initializez cu 0 vectorii pentru nivel si pentru intoarcere
vector<int> level(_n + 1, 0);
vector<int> back(_n + 1, 0);
stack<int> s;
for (int i = 1; i <= _n; i++) {
//pentru fiecare nod, in functia biconexe incep sa calculez nivelul daca acesta nu este inca setat
if (!level[i]) {
biconexe(i, 0, s, level, back, bic);
//golesc stiva
while (!s.empty()) {
s.pop();
}
}
}
return bic;
}
void Graph::addEdges() {
int x, y, i;
for (i = 0; i < _m; i++) {
f >> x >> y;
_list[x].push_back(y);
_list[y].push_back(x);
}
}
int main() {
int n, m;
f >> n >> m;
Graph gr(n, m);
gr.addEdges();
vector<vector<int>> bic = gr.c_bic();
g << bic.size() << '\n';
for (int i = 0; i < bic.size(); i++) {
for (int j = 0; j < bic[i].size(); j++)
g << bic[i][j] << " ";
g << '\n';
}
f.close();
g.close();
return 0;
}