Pagini recente » Cod sursa (job #1110384) | Cod sursa (job #1159347) | Cod sursa (job #360355) | Cod sursa (job #1826454) | Cod sursa (job #3001525)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
int lowlink[100001],indice[100001];
bool viz[100001];
stack<int>st;
int cnt,n,m;
vector<int>adiacenta[100001],rasp[100001];
void DFS(int nod,int nivel)
{
viz[nod] = 1;
lowlink[nod] = indice[nod] = nivel;
st.push(nod);
for(auto x:adiacenta[nod])
{
int curent = x;
if(!viz[curent])
{
DFS(curent,nivel+1);
if(lowlink[curent]>=indice[nod])
{
cnt++;
while(st.top()!=curent)
{
rasp[cnt].push_back(st.top());
st.pop();
}
rasp[cnt].push_back(st.top());
st.pop();
rasp[cnt].push_back(nod);
}
lowlink[nod] = min(lowlink[curent],lowlink[nod]);
}
else
{
lowlink[nod] = min(indice[curent],lowlink[nod]);
}
}
}
int main()
{
f >> n>>m;
for(int i=1;i<=m;i++)
{
int x,y;
f >> x >> y;
adiacenta[x].push_back(y);
adiacenta[y].push_back(x);
}
DFS(1,1);
g<< cnt<<'\n';
for(int i =1;i<=cnt;i++)
{
for(auto x:rasp[i])
{
g << x<< " ";
}
g << endl;
}
}