Pagini recente » Cod sursa (job #1696280) | Rating Popescu Robert Daniel (aisan) | Cod sursa (job #468079) | Cod sursa (job #2414741) | Cod sursa (job #1869737)
#include <cstdio>
#include <cstring>
using namespace std;
FILE *f, *g;
///Lista de arce
int k;
int nod[200001];
int urm[200001];
int lst[100001];
///Componente biconexe
int bic;
int nbic[200001];
int ubic[200001];
int lbic[100001];
int n, m;
int biComp;
int timp;
int dfn[100001];
int low[100001];
///Stiva
bool onStack[100001];
struct muchie
{
int st, dr;
};
muchie stk[100001];
int stkLen;
inline 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);
}
fclose(f);
}
void dfs(int u, int tata)
{
dfn[u] = low[u] = ++ timp;
int p = lst[u];
int st, dr;
while(p != 0)
{
// printf("%d %d %d\n", u, tata, nod[p]);
///Nod adiacent, diferit de tata, deasupra lui u in arborel DFS, pun muchia in stiva
if(nod[p] != tata && dfn[nod[p]] < dfn[u])
{
stk[++ stkLen].st = u;
stk[stkLen].dr = nod[p];
}
///Muchie "arbore"
if(dfn[nod[p]] == 0)
{
dfs(nod[p], u);
low[u] = mna(low[u], low[nod[p]]);
///u Punct de articulatie
if(low[nod[p]] >= dfn[u])
{
///Eticheteaza si scoate componenta biconexa de pe stiva
biComp ++;
memset(onStack, 0, sizeof(onStack));
do
{
st = stk[stkLen].st;
dr = stk[stkLen].dr;
stkLen --;
// printf("*%d ", n);
if(onStack[st] == 0)
{
onStack[st] = 1;
///Adauga la componenta biconexa curenta
bic ++;
nbic[bic] = st;
ubic[bic] = lbic[biComp];
lbic[biComp] = bic;
}
if(onStack[dr] == 0)
{
onStack[dr] = 1;
///Adauga la componenta biconexa curenta
bic ++;
nbic[bic] = dr;
ubic[bic] = lbic[biComp];
lbic[biComp] = bic;
}
}
while(st != u && dr != nod[p]);
// printf("\n");
}
}
///Muchie "inapoi"
else
if(nod[p] != tata)
low[u] = mna(low[u], dfn[nod[p]]);
///Urmatorul vecin
p = urm[p];
}
}
void solve()
{
dfs(1, -1);
}
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;
}