Pagini recente » Cod sursa (job #282828) | Cod sursa (job #1029138) | Cod sursa (job #282655) | Cod sursa (job #1571076) | Cod sursa (job #2404490)
#include <fstream>
#include <vector>
#include <algorithm>
#define nmax 100100
using namespace std;
vector<int> adj[nmax];
vector<int> sol[2 * nmax];
vector<pair<int,int>> s;
int low[nmax], discovered[nmax], visited[nmax];
int nr;
void dfs(int nod, int pre) {
low[nod] = discovered[nod] = discovered[pre] + 1;
visited[nod] = 1;
for (auto i = adj[nod].begin(); i != adj[nod].end(); i++) {
if (!visited[*i]) {
s.push_back(make_pair(nod, *i));
dfs(*i, nod);
low[nod] = min(low[nod], low[*i]);
if (low[*i] >= discovered[nod]) {
nr++;
while (s.back().first != nod) {
sol[nr].push_back(s.back().second);
s.pop_back();
}
sol[nr].push_back(nod);
sol[nr].push_back(s.back().second);
s.pop_back();
}
} else {
low[nod] = min(discovered[*i], low[nod]);
}
}
}
int main() {
int m, n, x, y, i;
ifstream read("biconex.in");
ofstream write("biconex.out");
read >> n >> m;
while (m--) {
read >> x >> y;
adj[x].push_back(y);
adj[y].push_back(x);
}
dfs(1, 0);
write << nr << '\n';
for(i = 1; i <= nr; i++) {
for(auto it = sol[i].begin(); it != sol[i].end(); it++) {
write << *it << ' ';
}
write<<'\n';
}
return 0;
}