Pagini recente » Cod sursa (job #2381946) | Cod sursa (job #563931) | drum-bugetat | Cod sursa (job #2451520) | Cod sursa (job #530329)
Cod sursa(job #530329)
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int N = 100001;
const int M = 200001;
struct muchie
{
int a,b;
};
int n;
vector<int> vecin[N];
bool vizitat[N];
int tata[N];
muchie stiva[M];int nstiva;
vector<int> sol[N]; int nsol;
int c[N],niv[N];
void citire()
{
int a,b,m;
scanf("%i%i",&n,&m);
for (int i = 1; i <= m; ++i)
{
scanf("%i%i",&a,&b);
vecin[a].push_back(b);
vecin[b].push_back(a);
}
}
void dfs(int nod)
{
vizitat[nod] = true;
c[nod] = niv[nod]; //c[i] -> nivelul cel mai de sus (minima) la care pot ajunge din subarborele lui i
for (int i = 0; i < vecin[nod].size(); ++i)
{
int fiu = vecin[nod][i];
if (!vizitat[nod])
{
tata[fiu] = nod;
niv[fiu] = niv[nod] + 1;
stiva[++nstiva].a = nod;
stiva[nstiva].b = fiu;
dfs(fiu);
if (c[nod] > c[fiu])
c[nod] = c[fiu];
//am gasit o componenta biconexa
if (niv[nod] <= c[fiu])
{
++nsol;
while (!(stiva[nstiva].a == nod && stiva[nstiva].b == fiu))
{
sol[nsol].push_back(stiva[nstiva].a);
sol[nsol].push_back(stiva[nstiva].b);
--nstiva;
}
sol[nsol].push_back(stiva[nstiva].a);
sol[nsol].push_back(stiva[nstiva].b);
--nstiva;
}
else
if (tata[nod] != fiu && niv[fiu] < niv[nod])
{
if (c[nod] > niv[fiu])
c[nod] = niv[fiu];
stiva[++nstiva].a = nod;
stiva[nstiva].b = fiu;
}
}
}
}
void afisare()
{
printf("%i\n",nsol);
for (int i = 1; i <= nsol; ++i)
{
sort(sol[i].begin(),sol[i].end());
for (int j = 0; j < sol[i].size(); ++j)
if ((j < sol[i].size() - 1 && sol[i][j] != sol[i][j + 1]) || j == sol[i].size() - 1)
printf("%i ",sol[i][j]);
printf("\n");
}
}
int main()
{
freopen("biconex.in","r",stdin);
freopen("biconex.out","w",stdout);
citire();
dfs(1);
afisare();
return 0;
}