Pagini recente » Atasamentele paginii Clasament cnrv_5 | Monitorul de evaluare | Monitorul de evaluare | Cod sursa (job #274740) | Cod sursa (job #1689825)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
const int NMAX = 100005;
vector <int> graph[NMAX];
vector <vector <int> > sol;
stack <pair <int, int> > _stack;
void extract(pair <int, int> edge) {
vector <int> aux;
while (_stack.top() != edge) {
aux.push_back(_stack.top().second);
_stack.pop();
}
aux.push_back(_stack.top().first);
aux.push_back(_stack.top().second);
_stack.pop();
sol.push_back(aux);
}
int h[NMAX];
int low[NMAX];
bool vis[NMAX];
void dfs(int node) {
vis[node] = true;
low[node] = h[node];
for (auto it: graph[node]) {
if (!vis[it]) {
h[it] = 1 + h[node];
_stack.push(make_pair(node, it));
dfs(it);
if (low[it] < low[node])
low[node] = low[it];
else if (low[it] >= h[node])
extract(make_pair(node, it));
}
else if (h[it] < low[node])
low[node] = h[it];
}
}
int main()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n = 0, m = 0;
cin >> n >> m;
int a, b;
while (m --) {
cin >> a >> b;
graph[a].push_back(b);
graph[b].push_back(a);
}
h[1] = 1;
dfs(1);
cout << sol.size() << '\n';
for (auto it: sol)
for (int i = 0; i < it.size(); ++ i)
cout << it[i] << " \n"[i + 1 == it.size()];
cin.close();
cout.close();
return 0;
}