Pagini recente » Cod sursa (job #951115) | Cod sursa (job #2830128) | Cod sursa (job #225642) | Cod sursa (job #978778) | Cod sursa (job #883826)
Cod sursa(job #883826)
#include<fstream>
#include<vector>
#include<algorithm>
#include<stack>
#define NMAX 100005
#define vec G[nod][i]
#define X s.top().first
#define Y s.top().second
using namespace std;
int n,m,lev[NMAX],c;
vector<int> G[NMAX],sol[NMAX];
stack<pair<int,int> > s;
int use[NMAX];
void read()
{
ifstream fin("biconex.in");
fin>>n>>m;
int x,y;
for(int i=0;i<m;i++)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
fin.close();
}
void clear(int x,int y)
{
while(X!=x && Y!=y)
{
sol[c].push_back(Y);
s.pop();
}
sol[c].push_back(y);
sol[c++].push_back(x);
s.pop();
}
void DFS(int nod,int TT)
{
use[nod]=use[TT]+1;
lev[nod]=use[nod];
for(size_t i=0;i<G[nod].size();i++)
if(!use[vec])
{
s.push(make_pair(nod,vec));
DFS(vec,nod);
lev[nod]=min(lev[nod],lev[vec]);
if(lev[vec]>=use[nod])
clear(nod,vec);
}
else
if(vec!=TT)
lev[nod]=min(lev[nod],lev[vec]);
}
void print()
{
ofstream fout("biconex.out");
fout<<c<<'\n';
for(int i=0;i<c;i++,fout<<'\n')
for(size_t j=0;j<sol[i].size();j++)
fout<<sol[i][j]<<' ';
fout.close();
}
int main()
{
read();
s.push(make_pair(1,0));
DFS(1,0);
print();
return 0;
}