Pagini recente » Cod sursa (job #113809) | Cod sursa (job #561890) | Cod sursa (job #3271590)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
vector<int> G[100005];
int nivel[100005], nma[100005], vis[100005];
stack<int> s;
vector<int> temp;
vector<vector<int>> biconexe;
void dfs(int k, int parent)
{
vis[k] = 1;
nivel[k] = nivel[parent] + 1;
nma[k] = nivel[k];
s.push(k);
for(int x : G[k])
{
if(x == parent)
continue;
if(vis[x])
{
if(nma[k] > nivel[x])
nma[k] = nivel[x];
}
else
{
dfs(x, k);
if(nma[k] > nma[x])
nma[k] = nma[x];
//if(nivel[k] <= nma[x])
//cout << k << endl;
//if(nivel[k] < nma[x])
// cout << k << " " << x << endl;
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()
{
ifstream cin("biconex.in");
ofstream cout("biconex.out");
int n, m, x, y;
cin >> n >> m;
for(int i=0;i<m;i++)
{
cin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1, 0);
cout << biconexe.size() << '\n';
for(auto i : biconexe)
{
for(int j : i)
cout << j << " ";
cout << '\n';
}
return 0;
}