Pagini recente » Cod sursa (job #1527862) | Cod sursa (job #907919) | Cod sursa (job #252351) | Cod sursa (job #2154536) | Cod sursa (job #1540483)
#include<fstream>
#include<vector>
#include<deque>
#include<algorithm>
using namespace std;
vector <int> L[100010], sol[100010];
deque <pair<int, int> > q;
pair <int, int> top;
int n, m, x, y, i, j, nrsol, low[100010], dfx[100010], nrqq;
void biconex (int nod, int fiu)
{
nrsol++;
do
{
top=q.back();
sol[nrsol].push_back(top.first);
sol[nrsol].push_back(top.second);
q.pop_back();
}
while(top.first!=nod && top.second!=fiu);
}
void dfsx (int nod, int niv, int tata)
{
low[nod]=dfx[nod]=niv;
for(int i=0; i<L[nod].size(); i++)
{
int fiu=L[nod][i];
if(fiu!=tata)
{
if(dfx[fiu]==0)
{
q.push_back(make_pair(nod, fiu));
dfsx(fiu, niv+1, nod);
low[nod]=min(low[nod], low[fiu]);
if(low[fiu]>=dfx[nod])
biconex(nod, fiu);
}
else
{
low[nod]=min(low[nod], dfx[fiu]);
}
}
}
}
ifstream in("biconex.in");
ofstream out("biconex.out");
int main()
{
in>>n>>m;
for(i=1; i<=m; i++)
{
in>>x>>y;
L[x].push_back(y);
L[y].push_back(x);
}
dfsx(1, 1, 0);
out<<nrsol<<"\n";
for(i=1; i<=nrsol; i++)
{
sort(sol[i].begin(), sol[i].end());
for(j=0; j<sol[i].size(); j++)
{
if(sol[i][j]!=sol[i][j+1])
out<<sol[i][j]<<" ";
}
out<<"\n";
}
return 0;
}