Pagini recente » Cod sursa (job #2801467) | Cod sursa (job #1211485) | Cod sursa (job #3201830) | Cod sursa (job #2285645) | Cod sursa (job #639932)
Cod sursa(job #639932)
#include <fstream>
#include <vector>
#define maxn 100001
#define maxm 200001
using namespace std;
ifstream f("biconex.in");
ofstream g("biconex.out");
int n,m,k,poz;
bool viz[maxn];
vector <int> muchii[maxn],sol[maxn];
int lvlmin[maxn],lvl[maxn];
struct muchie
{
int a,b;
}leg[maxm];
void df(int nod,int tata)
{
int aux,i;
viz[nod]=1;
lvlmin[nod]=lvl[tata]+1;
lvl[nod]=lvl[tata]+1;
for(i=0;i<muchii[nod].size();i++)
{
aux=muchii[nod][i];
if(!viz[aux])
{
poz++;
leg[poz].a=nod;
leg[poz].b=aux;
df(aux,nod);
if(lvl[nod]<=lvlmin[aux])
{
k++;
while(leg[poz].a!=nod && leg[poz].b!=aux)
{
sol[k].push_back(leg[poz].b);
poz--;
}
sol[k].push_back(leg[poz].b);
sol[k].push_back(leg[poz].a);
poz--;
}
lvlmin[nod]=min(lvlmin[nod],lvlmin[aux]);
continue;
}
else{
if(aux!=tata)
if(lvlmin[nod]>lvl[aux])
lvlmin[nod]=lvl[aux];
}
}
}
int main()
{
f>>n>>m;
for(;m;m--)
{
int x,y;
f>>x>>y;
muchii[x].push_back(y);
muchii[y].push_back(x);
}
for(int i=1;i<=n;i++)
if(!viz[i]) df(i,1);
g<<k<<"\n";
for(int i=1;i<=n;i++)
{
for(int j=sol[i].size()-1;j>=0;j--)
g<<sol[i][j]<<" ";
g<<"\n";
}
return 0;
}