Pagini recente » Cod sursa (job #67486) | Cod sursa (job #899799) | Cod sursa (job #54174) | Cod sursa (job #1398168) | Cod sursa (job #1428234)
#include<fstream>
#include<bitset>
#include<vector>
#include<algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector<int> v[100001];
bitset<100001> viz;
int low[100001];
int tata[100001];
int dft[100001];
vector<int> st;
vector<vector<int>> sol;
int cnt = 0;
void get_sol(int x, int y)
{
vector<int> aux;
sol.push_back(aux);
while (st.back()!=y)
{
sol[sol.size() - 1].push_back(st.back());
st.pop_back();
}
st.pop_back();
sol[sol.size() - 1].push_back(x);
sol[sol.size() - 1].push_back(y);
}
void dfs(int x,int f)
{
dft[x] = low[x] = ++cnt;
for (auto it : v[x])
{
if (it != f)
{
if (!dft[it])
{
st.push_back(it);
dfs(it, x);
low[x] = min(low[it], low[x]);
if (low[it] >= dft[x])
get_sol(x, it);
}
else
{
low[x] = min(low[x], dft[it]);
}
}
}
}
int main()
{
int n, m;
fin >> n >> m;
for (int i = 1; i <= m; i++)
{
int x, y;
fin >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1, 0);
fout << sol.size() << '\n';
for (int i = 0; i < sol.size(); i++)
{
for (int j = 0; j < sol[i].size(); j++)
{
fout << sol[i][j] << ' ';
}
fout << '\n';
}
}