Pagini recente » Cod sursa (job #1291413) | Cod sursa (job #1449872) | Cod sursa (job #1368030) | Cod sursa (job #2321498) | Cod sursa (job #3271938)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
vector <int> v[100005];
int nivel[100005], nma[100005], vis[100005];
stack <int> s;
vector <int> temp;
vector < vector <int> > biconexe;
void f(int k, int parent)
{
vis[k] = 1;
nivel[k] = nivel[parent] + 1;
nma[k] = nivel[k];
s.push(k);
for(int x : v[k])
{
if(x == parent)
continue;
if(vis[x])
{
if(nma[k] > nivel[x])
nma[k] = nivel[x];
}
else
{
f(x, k);
if(nma[k] > nma[x])
nma[k] = nma[x];
if(nivel[k] <= nma[x])
{
while(s.top() != x)
{
temp.push_back(s.top());
s.pop();
}
s.pop();
temp.push_back(x);
temp.push_back(k);
biconexe.push_back(temp);
temp.clear();
}
}
}
}
int main()
{
int n, m, x, y;
in >> n >> m;
for(int i = 1; i <= m; i ++)
{
in >> x >> y;
v[x].push_back(y);
v[y].push_back(x);
}
f(1, 0);
out << biconexe.size() << '\n';
for(auto i : biconexe)
{
for(int j : i)
out << j << " ";
out << '\n';
}
return 0;
}