Pagini recente » Cod sursa (job #3176247) | Cod sursa (job #2020028) | Cod sursa (job #1305076) | Cod sursa (job #1727751) | Cod sursa (job #432368)
Cod sursa(job #432368)
#include<fstream>
#include<vector>
#define nmax 100100
using namespace std;
vector <int> v[nmax],sol[2*nmax];
vector <pair <int, int> > s;
int acc[nmax],niv[nmax],u[nmax];
int nr;
void dfs(int nod, int pre)
{
acc[nod]=niv[nod]=niv[pre]+1;
u[nod]=1;
vector<int> :: iterator fiu;
for(fiu=v[nod].begin();fiu!=v[nod].end();fiu++)
if(*fiu!=pre)
if(!u[*fiu])
{
s.push_back(make_pair(nod,*fiu));
dfs(*fiu,nod);
if(acc[nod]>acc[*fiu])
acc[nod]=acc[*fiu];
if(acc[*fiu]>=niv[nod])
{
nr++;
while(s.back().first!=nod)
{
sol[nr].push_back(s.back().second);
s.pop_back();
}
sol[nr].push_back(nod);
sol[nr].push_back(s.back().second);
s.pop_back();
}
}
else
if(acc[nod]>niv[*fiu])
acc[nod]=niv[*fiu];
}
int main()
{
int m,x,y,i,n;
ifstream read("biconex.in");
ofstream write("biconex.out");
read>>n>>m;
while(m--)
{
read>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
dfs(1,0);
write<<nr<<'\n';
vector<int> :: iterator fiu;
for(i=1;i<=nr;i++)
{
for(fiu=sol[i].begin();fiu!=sol[i].end();fiu++)
write<<*fiu<<' ';
write<<'\n';
}
return 0;
}