Pagini recente » Cod sursa (job #1062044) | Diferente pentru preoni-2007/runda-finala/poze/evaluare intre reviziile 4 si 5 | Cod sursa (job #828372) | Cod sursa (job #163348) | Cod sursa (job #1869751)
#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);
add(b, a);
}
fclose(f);
}
void dfs(int u, int tata)
{
dfn[u] = low[u] = ++ timp;
int p = lst[u];
int st, dr;
int x;
while(p != 0)
{
x = nod[p];
///Nod adiacent, diferit de tata, deasupra lui u in arborel DFS, pun muchia in stiva
if(x != tata && dfn[x] < dfn[u])
{
stk[++ stkLen].st = u;
stk[stkLen].dr = x;
}
///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 ++;
memset(onStack, 0, sizeof(onStack));
do
{
st = stk[stkLen].st;
dr = stk[stkLen].dr;
stkLen --;
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 != x && stkLen > 0);
}
}
///Muchie "inapoi"
else
if(x != tata)
low[u] = mna(low[u], dfn[x]);
///Urmatorul vecin
p = urm[p];
}
}
void solve()
{
int i;
for(i = 1; i <= n; i ++)
{
if(dfn[i] == 0)
stkLen = 0, dfs(i, -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;
}