Pagini recente » Cod sursa (job #1934426) | Cod sursa (job #1481385) | Cod sursa (job #1118559) | Cod sursa (job #430119) | Cod sursa (job #490833)
Cod sursa(job #490833)
#include<stdio.h>
#include<algorithm>
#include<vector>
#include<stack>
#define pb push_back
using namespace std;
stack <int> s1,s2;
vector<int>v[100010],sol[ 10010 ];
int i,j,k,lvl[ 100000 ],low[ 100010 ],T[ 100010 ],l,m,n;
void citire(){
freopen("biconex.in","r",stdin);
scanf("%d %d",&n,&m);
int a,b;
for(i = 1; i <= m; i++)
{scanf("%d %d",&a,&b);
v[a].pb(b);
v[b].pb(a);
}
}
void PushNewSol(int a,int b){
int x,y;
k++;
do{
x = s1.top();
y = s2.top();
sol[k].pb(x);
sol[k].pb(y);
s1.pop();
s2.pop();
}while(!(((a==x)&&(b==y))||((a==y)&&(b==x))) );
sort(sol[k].begin(),sol[k].end());
}
void dfs(int nod,int niv){
int N,f,i;
lvl[ nod] = low[nod] = niv;
N = v[nod].size();
for ( i = 0 ;i < N ; i++)
{f = v[nod][i];
if(!lvl[f])
{s1.push(nod);
s2.push(f);
T[f] = nod;
dfs(f,niv+1);
low[nod] = min(low[nod],low[f]);
if(low[f] >= lvl[nod])
PushNewSol(nod,f);
}
else
if(T[nod] != f)
low[nod] = min(low[nod],low[f]);
}
}
void afisare(){
freopen("biconex.out","w",stdout);
int i,j;
printf("%d\n",k);
for(i = 1; i <= k ; i++)
{for(j = 0; j < sol[i].size();j++)
if(sol[i][j] != sol[i][j+1])
printf("%d ",sol[i][j]);
printf("\n");
}
}
int main(){
citire();
dfs(1,1);
afisare();
return 0;}