Pagini recente » Cod sursa (job #2942769) | Cod sursa (job #1266589) | Cod sursa (job #982761) | Cod sursa (job #197397) | Cod sursa (job #1471288)
#include<cstdio>
using namespace std;
const int mMax = 200000, nMax = 100000;
int val[mMax * 2], urm[mMax * 2], lst[nMax], st[nMax], nivel[nMax], low[nMax], sol[nMax * 2];
bool viz[nMax];
int n, m, nrc, vf, u, nrs, cnt, solPoz;
inline void adauga(int x, int y){
val[nrc] = y;
urm[nrc] = lst[x];
lst[x] = nrc;
nrc++;
}
void init(){
for(int i = 0 ; i < n ; i ++) lst[i] = -1;
}
void dfs(int nod, int par){
st[vf++] = nod;
viz[nod] = 1;
low[nod] = nivel[nod];
int vec = val[lst[nod]], poz = lst[nod];
while(vec > -1){
if(vec != par){
if(!viz[vec]){
nivel[vec] = nivel[nod] + 1;
dfs(vec, nod);
low[nod] = low[nod] < low[vec] ? low[nod] : low[vec];
if(low[vec] >= nivel[nod]){
u = st[--vf];
cnt = 1; nrs ++;
sol[solPoz + cnt] = u;
while(u != vec){
u = st[--vf]; ++ cnt;
sol[solPoz + cnt] = u;
}
++cnt;
sol[solPoz + cnt] = nod;
sol[solPoz] = cnt;
solPoz += cnt + 1;
}
}else if(nivel[vec] < nivel[nod]){
low[nod] = low[nod] < low[vec] ? low[nod] : low[vec];
}
}
poz = urm[poz];
vec = poz >= 0 ? val[poz] : -1;
}
}
int main (){
FILE *in = fopen("biconex.in","r");
fscanf(in,"%d%d", &n ,&m);
init();
int x, y;
for(int i = 0 ; i < m ; i++){
fscanf(in,"%d%d", &x, &y);
x--, y--;
adauga(x,y);
adauga(y,x);
}
for(int i = 0 ; i < n ; i++){
if(!viz[i])
dfs(i, - 1);
}
FILE *out = fopen("biconex.out","w");
fprintf(out,"%d\n", nrs);
int i = 0, tg;
while(i < solPoz){
cnt = sol[i++];
tg = i + cnt;
while(i < tg){
fprintf(out,"%d ", sol[i] + 1);
i++;
}
fprintf(out,"\n");
}
return 0;
}