Pagini recente » Cod sursa (job #1294661) | Cod sursa (job #1497000) | Cod sursa (job #1364168) | Cod sursa (job #1649991) | Cod sursa (job #2147031)
#include <fstream>
#include <vector>
#include <stack>
#define MAX 100005
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
vector<int> a[MAX];
vector< vector<int> > sol;
stack<int> st;
bool viz[MAX];
int nro[MAX],low[MAX];
int nrb,root;
int n,m,x,y;
void biconex(int x,int t){
viz[x]=true;
nro[x]=low[x]=nro[t]+1;
st.push(x);
for(int i=0 ; i<a[x].size() ; ++i)
{
int it=a[x][i];
if(it==t)
continue;
if(viz[it])
{
low[x]=min(low[x],nro[it]);
continue;
}
biconex(it, x);
low[x]=min(low[x],low[it]);
if(nro[x]<=low[it])
{
sol.push_back(vector<int>(0));
int z;
do{
z=st.top();
st.pop();
sol[nrb].push_back(z);
}while(z!=it);
sol[nrb].push_back(x);
++nrb;
}
}
}
int main()
{
f>>n>>m;
for(int i=1 ; i<=m; ++i)
{
f>>x>>y;
a[x].push_back(y);
a[y].push_back(x);
}
for(int i=1 ; i<=n ; ++i)
if (!viz[i])
{
root=i;
biconex(i,0);
}
g<<nrb<<'\n';
for(int i=0 ; i<sol.size() ; ++i)
{
for(int j=0 ; j<sol[i].size() ; ++j)
g<<sol[i][j]<<" ";
g<<'\n';
}
return 0;
}