Pagini recente » Cod sursa (job #2416466) | Cod sursa (job #984008) | Cod sursa (job #2003134) | Cod sursa (job #3272992) | Cod sursa (job #2965943)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
vector <int> G[100005];
typedef pair<int, int> muchie;
stack <muchie> st;
vector < vector<int>> rez;
int n,m,x,y;
bool bif[100005];
int lvl[100005], nma[100005];
void comp_bi(int x, int y)
{
int tx, ty;
vector <int> bx;
do
{
tx = st.top().first, ty = st.top().second;
bx.push_back(tx); bx.push_back(ty);
st.pop();
}while(tx!=x || ty!=y);
rez.push_back(bx);
}
void DFS(int nod, int fth, int hgh)
{
bif[nod]=1;
lvl[nod]=nma[nod]=hgh;
for(int i=0;i<G[nod].size();++i)
{
if(!bif[G[nod][i]])
{
st.push(muchie(nod, G[nod][i]));
DFS(G[nod][i], nod, hgh+1);
nma[nod]=min(nma[nod], nma[G[nod][i]]);
if(nma[G[nod][i]]>=lvl[nod])comp_bi(nod, G[nod][i]);
}
else if(G[nod][i]!=fth)nma[nod]=min(nma[nod], lvl[G[nod][i]]);
}
}
int main()
{
fin>>n>>m;
for(int i=1;i<=m;++i)
{
fin>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
DFS(1,0,1);
fout<<rez.size()<<'\n';
for(int i=0;i<rez.size();++i)
{
sort(rez[i].begin(), rez[i].end());
fout<<rez[i][0]<<' ';
for(int j=1;j<rez[i].size();++j)
if(rez[i][j]!=rez[i][j-1])fout<<rez[i][j]<<' ';
fout<<'\n';
}
//cout << "Hello world!" << endl;
return 0;
}