Pagini recente » Cod sursa (job #255800) | Cod sursa (job #129126) | Cod sursa (job #2909331) | Cod sursa (job #86733) | Cod sursa (job #3029958)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int n,m,tt[100001],nivel[100001],nma[100001],viz[100001],aux;
vector<int> G[100001],sol[100001];
void dfs(int x)
{
nivel[x]=nivel[tt[x]]+1;
nma[x]=nivel[x];
for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
{
int nod=*it;
if(nivel[nod]==0)
{
tt[nod]=x;
dfs(nod);
if(nma[x]>nma[nod]) nma[x]=nma[nod];
if(nivel[x]<nma[nod])
{
sol[++aux].push_back(x);
sol[aux].push_back(nod);
G[x].erase(it);
it--;
}
}
else if(nod!=tt[x])
{
nma[x]=min(nma[x],nivel[nod]);
}
}
}
void dfsc(int x, int aux)
{
viz[x]=1;
sol[aux].push_back(x);
for(vector<int>::iterator it=G[x].begin();it!=G[x].end();it++)
{
if(viz[*it]==0)
dfsc(*it,aux);
}
}
int main()
{
fin >> n >> m;
for(int i=1;i<=m;i++)
{
int x,y;
fin >> x >> y;
G[x].push_back(y);
G[y].push_back(x);
}
dfs(1);
aux++;
for(int i=1;i<=n;i++)
{
if(viz[i]==0)
{
dfsc(i,aux);
if(sol[aux].size()!=1)
aux++;
}
}
aux--;
fout << aux << "\n";
for(int i=1;i<=aux;i++)
{
sort(sol[i].begin(),sol[i].end());
for(vector<int>::iterator it=sol[i].begin();it!=sol[i].end();it++)
fout << *it << " ";
fout << "\n";
}
return 0;
}