Pagini recente » Cod sursa (job #1939868) | Cod sursa (job #2885686) | Cod sursa (job #2674766) | Cod sursa (job #5158) | Cod sursa (job #972457)
Cod sursa(job #972457)
#include <fstream>
#include <vector>
#include <stack>
using namespace std;
/**
dfn[x] = numarul de ordine al varfului x la parcurgerea DFS a grafului (depth-first-number)
low[x] = numarul de ordine al primului varf din parcurgerea DFS a grafului care poate fi atins pe un alt
lant decat lantul unic din arborele partial DFS
low[x] = min (dfn[x], min(low[y] | y este fiu al lui x), min(dfn[z] | [x, z] este muchie de intoarcere))
S = stiva in care retinem muchiile atat pe cele din arborele DFS cat si pe cele de intoarcere in
ordinea in care sunt intalnite in cadrul parcurgerii
*/
struct Muchie
{
int x, y;
};
stack <Muchie> S;
Muchie auxx;
int dfn[100010];
int low[100010];
const int start = 1;
int n, m, nrc, num, nrfii;
vector <int> G[100010];
vector <int> comp[100010];
inline int min(int x, int y)
{
return x<y?x:y;
}
inline void Read()
{
ifstream f ("biconex.in");
f>>n>>m;
int i, x, y;
for (i=1; i<=m; i++)
{
f>>x>>y;
G[x].push_back(y);
G[y].push_back(x);
}
}
inline void Initializare()
{
int i;
for (i=1; i<=n; i++)
dfn[i] = low[i] = -1;
Muchie aux;
/**
initializam stiva cu o muchie fictiva care in capete nodul 1 ca nod de start pentru DFS
si nodul fictiv -1
*/
aux.x = start;
aux.y = -1;
S.push(aux);
}
inline void CompBiconexa(int nod, int x)
{
nrc++;
Muchie p;
int nr = 0;
p = S.top();
while (!(p.x == nod && p.y == x))
{
nr++;
comp[nrc].push_back(p.y);
S.pop();
p = S.top();
}
comp[nrc].push_back(nod);
comp[nrc].push_back(x);
S.pop();
}
inline void Biconex(int nod, int tatanod)
{
/// nod este nodul curent iar tatanod este tatal lui
/// num ajuta la calcularea numarului de ordine al nodului curent in parcurgerea DFS
num++;
dfn[nod] = low[nod] = num;
int x;
vector <int>::iterator it;
for (it = G[nod].begin(); it!=G[nod].end(); it++)
{
x = *it; /// x este nod adiacent al lui nod;
/// daca x este diferit de tatal lui nod si daca x nu a mai fost vizitat sau
/// a mai fost vizitat dar inaintea lui nod (este back edge)
/// atunci muchia se adauga in stiva
/// a 2a conditie este pusa pentru a nu adauga de 2 ori aceeasi muchie
if (x != tatanod && dfn[x] < dfn[nod])
{
/// inseram in stiva S muchia [nod, x];
auxx.x = nod;
auxx.y = x;
S.push(auxx);
}
if (dfn[x] == -1) /// daca adiacentul nu a mai fost vizitat
{
if (nod == start) /// am gasit pe x ca fiind fiu al nodului start
nrfii++;
Biconex(x, nod); /// facem DFS din x amu
low[nod] = min(low[nod], low[x]);
if (low[x] >= dfn[nod]) /// daca nod este punct de articulatie
{
/// am gasit o componenta biconexa formata din muchiile din stiva S pana la
/// intalnirea muchiei [nod, x]
CompBiconexa(nod, x);
}
}
else
{
if (x != tatanod)
{
/// x nu este tatanod si x a mai fost vizitat ca de asta intra pe else
/// atunci inseamna ca muchia [nod, x] este muchie de intoarcere de la nod la x
low[nod] = min(low[nod], dfn[x]);
}
}
}
}
inline void Write()
{
ofstream g("biconex.out");
g<<nrc<<"\n";
int i;
vector <int>::iterator it;
for (i = 1; i<=nrc; i++)
{
for (it = comp[i].begin(); it!=comp[i].end(); it++)
g<<*it<<" ";
g<<"\n";
}
g.close();
}
int main()
{
Read();
Initializare();
Biconex(start, -1); /// DFS (start, tatastart);
Write();
return 0;
}