Pagini recente » Cod sursa (job #486476) | Cod sursa (job #283064) | Cod sursa (job #1072145) | Cod sursa (job #1657956) | Cod sursa (job #286776)
Cod sursa(job #286776)
#include <fstream.h>
#include <stdlib.h>
#define Nmax 100001
#define Mmax 200001
ifstream in("biconex.in");
ofstream out("biconex.out");
struct muchie{int x,y;} ST[Mmax];
int vf,n,m,num,cb,nrfii;
int DFN[Nmax],LOW[Nmax],s[Nmax];
int * A[Nmax], art[Nmax], *c[Nmax];
void initializare(){
for(int i=1;i<=n;++i)DFN[i] = LOW[i] = -1;
ST[0].x = 1; ST[0].y = -1;
}
void citire(){
int x,y,i;
in>>n>>m;
for(i=1;i<=n;++i){
A[i] = (int *)realloc(A[i], sizeof(int));
A[i][0] = 0;
c[i] = (int *)realloc(c[i], sizeof(int));
c[i][0] = 0;
}
for(i=1;i<=m;++i){
in>>x>>y;
A[x][0]++;
A[x] = (int *)realloc(A[x], (A[x][0]+1)*sizeof(int));
A[x][A[x][0]] = y;
A[y][0]++;
A[y] = (int *)realloc(A[y], (A[y][0]+1)*sizeof(int));
A[y][A[y][0]] = x;
}
}
int min(int x,int y){
if(x>y) return y;
return x;
}
void salveaza(int x, int y){
muchie p;
do{
p = ST[vf--];
if(s[p.x] != cb && p.x != x && p.x!=y){ // vecorul selectat e marcat cu numarul componentei conexe pt a evita adaugarea aceluiasi nod
c[cb][0]++;
c[cb] = (int *)realloc(c[cb],(c[cb][0]+1)*sizeof(int));
c[cb][c[cb][0]] = p.x;
s[p.x] = cb;
}
}while(p.x!=x || p.y!=y);
c[cb][0]++;
c[cb] = (int *)realloc(c[cb],(c[cb][0]+1)*sizeof(int));
c[cb][c[cb][0]] = x;
c[cb][0]++;
c[cb] = (int *)realloc(c[cb],(c[cb][0]+1)*sizeof(int));
c[cb][c[cb][0]] = y;
s[x] = s[y] = cb;
}
void comp_biconexe(int u, int tu){
int d; // descendent
DFN[u] = LOW[u] = ++num;
for(int i=1;i<=A[u][0];++i){
d = A[u][i];
if(d!=tu && DFN[d] < DFN[u]) // daca nu a mai fost vizitat
ST[++vf].x = d,ST[vf].y=u; // sau daca este muchie de intoarcere
if(DFN[d] == -1){ // daca nu a mai fost vizitat
if(u == 1) // daca u este radacina inseamna ca este un fiu al radacinii
nrfii++;
comp_biconexe(d,u); // parcurgere dfs
LOW[u] = min(LOW[u],LOW[d]); // se atribuie recursiv fiecarui nod u care are legatura cu x nodul cu deep-breath number(dfn) cel mai mic
if(LOW[d] >= DFN[u]){// nu exista muchie de la x la un stramos a lui u
// este punct de art
if(u!=1)art[u] = 1;
cb++;
salveaza(d,u);
}
}
else if(d!=tu) // nu a mai fost vizitat => muchie de intoarce de la u la x
LOW[u] = min(LOW[u],DFN[d]);
}
}
void afisare(){
int i,j;
out<<cb<<"\n";
for(i=1;i<=n;++i){
for(j=1;j<=c[i][0];++j)
out<<c[i][j]<<" ";
out<<"\n";
}
}
int main(){
citire();
initializare();
comp_biconexe(1,-1);
afisare();
return 0;
}