Pagini recente » Cod sursa (job #2461333) | Cod sursa (job #1120681) | Cod sursa (job #1388593) | Cod sursa (job #2768503) | Cod sursa (job #1385855)
#include <fstream>
using namespace std;
ifstream f ("biconex.in");
ofstream g ("biconex.out");
struct nod
{
int info;
nod *adr;
} *componente[100005], *v[100005], *s;
void adauga_vecin (int x, int y)
{
nod *c;
c = new nod;
c -> info = y;
c -> adr = v[x];
v[x] = c;
}
void adauga_componente (int nrc, int y)
{
nod *c;
c = new nod;
c -> info = y;
c -> adr = componente[nrc];
componente[nrc] = c;
}
void adauga_stiva (int info)
{
nod *c;
c = new nod;
c -> info = info;
c -> adr = s;
s = c;
}
void sterge_stiva ()
{
nod *p;
p = s;
s = s -> adr;
delete p;
}
int n, m, lowlink[100005], index[100005], nrcomp = 0;
bool viz[100005];
void citire ()
{
f >> n >> m;
int a, b;
for (int i = 1; i <= m; i ++)
{
f >> a >> b;
adauga_vecin (a, b);
adauga_vecin (b, a);
}
}
int minim (int a, int b)
{
if (a < b)
return a;
return b;
}
void dfs (int node, int nivel)
{
index[node] = nivel;
lowlink[node] = nivel;
viz[node] = 1;
adauga_stiva (node);
nod *c = v[node];
int curent;
while (c)
{
curent = c -> info;
if (viz[curent])
lowlink[node] = minim (lowlink[node], index[curent]);
else
{
dfs (curent, nivel + 1);
lowlink[node] = minim (lowlink[node], lowlink[curent]);
if (index[node] <= lowlink[curent])
{
++ nrcomp;
int de_adaugat;
do
{
de_adaugat = s -> info;
adauga_componente (nrcomp, de_adaugat);
sterge_stiva ();
}while (de_adaugat != curent);
adauga_componente (nrcomp, node);
}
}
c = c -> adr;
}
}
int main()
{
citire ();
for (int i = 1; i <= n; i ++)
if (! viz[i])
dfs (i, 1);
g << nrcomp << '\n';
nod *c;
for (int i = 1; i <= nrcomp; i ++)
{
c = componente[i];
while (c)
{
g << c -> info << " ";
c = c -> adr;
}
g << '\n';
}
f.close ();
g.close ();
return 0;
}