Pagini recente » Cod sursa (job #2815331) | Cod sursa (job #223611) | Cod sursa (job #127593) | Cod sursa (job #2857918) | Cod sursa (job #3030187)
#include <fstream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
ifstream fin("biconex.in");
ofstream fout("biconex.out");
int c,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);
G[nod].erase(lower_bound(G[nod].begin(),G[nod].end(),x));
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);
}
for(int i=1; i<=n; i++)
sort(G[i].begin(),G[i].end());
dfs(1);
aux++;
for(int i=1; i<=n; i++)
{
if(viz[i]==0)
{
dfsc(i,aux);
if(sol[aux].size()!=1)
{
aux++;
}
else sol[aux].clear();
}
}
aux--;
fout << aux << "\n";
for(int i=1; i<=aux; i++)
{ for(vector<int>::iterator it=sol[i].begin(); it!=sol[i].end(); it++)
fout << *it << " ";
fout << "\n";
}
return 0;
}