Pagini recente » Cod sursa (job #2812631) | Cod sursa (job #202009) | Cod sursa (job #242867) | Cod sursa (job #1245128) | Cod sursa (job #2689975)
#include <iostream>
#include <fstream>
#include <vector>
#include <stack>
#define NMAX 100002
using namespace std;
ifstream fin ("biconex.in");
ofstream fout ("biconex.out");
vector<int>v[NMAX], afis[NMAX];
stack<pair<int, int> >st;
int tt[NMAX], d[NMAX];
int nr_componente=0;
int DFS(int x)
{
int i, low, lowV, u;
d[x]=d[tt[x]]+1;
low=d[x];
for(i=0; i<v[x].size(); i++)
{
u=v[x][i];
if(u!=tt[x])
{
if(d[u]>0) low=min(low, d[u]);
else
{
tt[u]=x;
st.push({x, u});
lowV=DFS(u);
if(lowV>=d[x]) //am gasit un punct de articulatie
{
nr_componente++;
while(st.top().first!=x || st.top().second!=u)
{
afis[nr_componente].push_back(st.top().second);
st.pop();
}afis[nr_componente].push_back(st.top().second); afis[nr_componente].push_back(st.top().first);
st.pop();
}
low=min(low, lowV);
}
}
}
return low;
}
int main()
{
int n, m, i, j, x, y;
fin>>n>>m;
for(i=1; i<=m; i++)
{
fin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
//tt[1]=0;
DFS(1);
fout<<nr_componente<<"\n";
for(i=1; i<=nr_componente; i++)
{
for(j=afis[i].size()-1; j>=0; j--)
{
fout<<afis[i][j]<<' ';
}
fout<<"\n";
}
}