Pagini recente » Cod sursa (job #2284951) | Cod sursa (job #1851386) | Cod sursa (job #2887120) | Cod sursa (job #1157836) | Cod sursa (job #732260)
Cod sursa(job #732260)
#include<iostream>
#include<fstream>
#include<vector>
#define nmax 100001
#define min(a,b) (a<b)? a: b
using namespace std;
int n,m,vf=-1,k,viz[nmax],c[nmax],niv[nmax];
vector <int> s[nmax],v[nmax];
struct muchie{
int a;
int b;
}stiva[nmax];
void DFS(int i){
viz[i]=1;
c[i]=niv[i];
for(int j=0;j<v[i].size();j++)
if(viz[v[i][j]]==0){
niv[v[i][j]]=niv[i]+1;
vf++;
stiva[vf].a=i;
stiva[vf].b=v[i][j];
DFS(v[i][j]);
if(c[v[i][j]]>=niv[i]){
while(stiva[vf].a!=i&&stiva[vf].b!=v[i][j]){
s[k].push_back(stiva[vf].b);
vf--;
}
s[k].push_back(i);
s[k].push_back(v[i][j]);
vf--;
k++;
}
c[i]=min(c[i],c[v[i][j]]);
}
else
c[i]=min(c[i],niv[v[i][j]]);
}
int main(){
ifstream f("biconex.in");
ofstream g("biconex.out");
int x,y;
f>>n>>m;
for(int i=1;i<=m;i++){
f>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
DFS(1);
g<<k<<endl;
for(int i=0;i<k;i++){
for(int j=0;j<s[i].size();j++)
g<<s[i][j]<<" ";
g<<"\n";
}
return 0;
}