Pagini recente » Cod sursa (job #3263121) | Cod sursa (job #758582) | Cod sursa (job #1006586) | Cod sursa (job #2777224) | Cod sursa (job #2374175)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n, m, f[100005], d[100005], step, biconex;
bool in_stack[100005];
vector <int> v[100005], ans[100005];
stack <int> st;
void Tarjan(int nod, int father)
{
f[nod] = d[nod] = ++step;
st.push(nod);
for(int i = 0; i < v[nod].size(); i++)
{
int child = v[nod][i];
if(child == father) continue;
if(d[child])
{
f[nod] = min(f[nod], f[child]);
continue;
}
Tarjan(child, nod);
f[nod] = min(f[nod], f[child]);
if(f[child] >= d[nod])
{
biconex++;
while(!st.empty() && st.top() != nod)
{
ans[biconex].push_back(st.top());
st.pop();
}
st.pop();
ans[biconex].push_back(nod);
ans[biconex].push_back(child);
}
}
}
int main()
{
fin >> n >> m;
for(int i = 1; i <= m; i++)
{
int a, b;
fin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
Tarjan(1, 0);
fout << biconex << '\n';
for(int i = 1; i <= biconex; i++)
{
for(int j = 0; j < ans[i].size(); j++)
fout << ans[i][j] << " ";
fout << '\n';
}
return 0;
}