Pagini recente » Cod sursa (job #1910313) | Cod sursa (job #1215383) | Cod sursa (job #751876) | Cod sursa (job #1869786)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f, *g;
///Lista de muchii
int k;
int nod[2000001];
int urm[2000001];
int lst[1000001];
///Componente biconexe
int bic;
int nbic[2000001];
int ubic[2000001];
int lbic[1000001];
int n, m;
int biComp;
int timp;
int dfn[1000001];
int low[1000001];
///Stiva
int stk[1000001];
int stkLen;
int mna(int a, int b)
{
return(a < b ? a : b);
}
void add(int a, int b)
{
k ++;
nod[k] = b;
urm[k] = lst[a];
lst[a] = k;
}
void readFile()
{
f = fopen("biconex.in", "r");
fscanf(f, "%d%d", &n, &m);
int i;
int a, b;
for(i = 1; i <= m; i ++)
{
fscanf(f, "%d%d", &a, &b);
add(a, b);
add(b, a);
}
fclose(f);
}
void dfs(int u, int parent)
{
dfn[u] = dfn[parent] + 1;
low[u] = dfn[u];
int p = lst[u];
int st, dr;
int x, nodVecin;
stk[++ stkLen] = u;
while(p != 0)
{
x = nod[p];
if(x != parent)
{
///Muchie "arbore"
if(dfn[x] == 0)
{
dfs(x, u);
low[u] = mna(low[u], low[x]);
///u Punct de articulatie
if(low[x] >= dfn[u])
{
///Eticheteaza si scoate componenta biconexa de pe stiva
biComp ++;
bic ++;
nbic[bic] = u;
ubic[bic] = lbic[biComp];
lbic[biComp] = bic;
///Adauga la componenta curenta
do
{
nodVecin = stk[stkLen --];
bic ++;
nbic[bic] = nodVecin;
ubic[bic] = lbic[biComp];
lbic[biComp] = bic;
}
while(nodVecin != x && stkLen > 0);
}
}
///Muchie "inapoi"
else
low[u] = mna(low[u], dfn[x]);
}
///Urmatorul vecin
p = urm[p];
}
}
void solve()
{
dfs(1, 0);
}
void printFile()
{
g = fopen("biconex.out", "w");
fprintf(g, "%d\n", biComp);
int i, p;
for(i = 1; i <= biComp; i ++)
{
p = lbic[i];
while(p != 0)
{
fprintf(g, "%d ", nbic[p]);
p = ubic[p];
}
fprintf(g, "\n");
}
}
int main()
{
readFile();
solve();
printFile();
return 0;
}