Pagini recente » Cod sursa (job #1445241) | Cod sursa (job #3182665) | Cod sursa (job #2269383) | Cod sursa (job #2661234) | Cod sursa (job #2873050)
#include <bits/stdc++.h>
using namespace std;
ifstream in("biconex.in");
ofstream out("biconex.out");
const int N=1e5;
struct graf
{
vector<int> v;
}la[N+5];
vector<vector<int> >biconex;
int nivel[N+5],nma[N+5],nrBiconex;
stack <int> stk;
void dfs(int rad,int nod,int tata)
{
if(tata == -1) nma[nod]=nivel[nod]=1;
else nma[nod]=nivel[nod]=nivel[tata]+1;
stk.push(nod);
for(int i=0;i<la[nod].v.size();i++)
{
int to=la[nod].v[i];
if(!nivel[to])
{
dfs(rad,to,nod);
nma[nod]=min(nma[nod],nma[to]);
if( nivel[nod] <= nma[to])
{
nrBiconex++;
vector <int> aux;
while(stk.top()!=to)
{
aux.push_back(stk.top());
stk.pop();
}
aux.push_back(stk.top());
stk.pop();
aux.push_back(nod);
biconex.push_back(aux);
}
}
else nma[nod]=min(nma[nod],nivel[to]);
}
}
int main()
{
int n,m;
in>>n>>m;
for(int i=1; i<=m; i++)
{
int x,y;
in>>x>>y;
la[x].v.push_back(y);
la[y].v.push_back(x);
}
for(int i=1;i<=n;i++)
if(!nivel[i]) dfs(i,i,-1);
out<<nrBiconex<<'\n';
for(int i=0;i<biconex.size();i++)
{
for(int j=0;j<biconex[i].size();j++)
out<<biconex[i][j]<<' ';
out<<'\n';
}
}