Ktra bo phan lien thong manh

#define MAX_ELEMENTS 100 #include<stdio.h> typedef int ElementType; typedef struct { ElementType data[MAX_ELEMENTS]; int size; } List; /* Tao danh sach rong */ void make_null(List* L) { L->size = 0; } /* Them mot phan tu vao cuoi danh sach */ void push_back(List* L, ElementType x) { L->data[L->size] = x; L->size++; } /* Lay phan tu tai vi tri i, phan tu bat dau o vi tri 1 */ ElementType element_at(List* L, int i) { return L->data[i-1]; } /* Tra ve so phan tu cua danh sach */ int count_list(List* L) { return L->size; } #define MAX_VERTEXES 100 /* Tim cac dinh ke cua dinh x */ typedef struct { int n; /* n: so dinh */ /* ma tran dinh – dinh */ int A [MAX_VERTEXES][MAX_VERTEXES]; } Graph; /* Khoi tao do thi G co n dinh */ void init_graph(Graph* G, int n) { int i, j; G->n = n; for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) G->A[i][j] = 0; } /* Them cung e = (x, y) vao do thi G */ void add_edge(Graph* G, int x, int y) { G->A[x][y] += 1; } /*kiem tra xem x y co ke nhau k*/ int adjacent(Graph* G, int x, int y) { return G->A[x][y] != 0; } /* Tinh bac cua dinh x: deg(x) */ int degree(Graph* G, int x) { int y, deg = 0; for (y = 1; y <= G->n; y++) deg+=G->A[x][y]; return deg; } // danh sach cac dinh ke cua x; List neighbors(Graph* G, int x) { int y; List list; make_null(&list); for(y = 1; y <= G->n; y++) if (adjacent(G, x, y)) push_back(&list, y); return list; } /*===============KHOI TAO STACK==============*/ #define MAX_ELEMENTS 100 typedef struct { int data[MAX_ELEMENTS]; int size; } Stack; void make_null_stack(Stack* S) { S->size = 0; } void push(Stack* S, int x) { S->data[S->size] = x; S->size++; } int top(Stack* S) { return S->data[S->size - 1]; } void pop(Stack* S) { S->size--; } int empty(Stack* S) { return S->size == 0; } /*==============GIAI THUAT TARJAN===========*/ //ham min int min(int a,int b) { if(a<b) return a; return b; } #define MAX_STACK 1000 int k; int on_stack[MAX_STACK]; int num[MAX_VERTEXES]; int min_num[MAX_VERTEXES]; Stack S; int strong_connect(Graph *G, int x){ int count = 0; // them bien count dem so BPLT num[x] = min_num[x] = k; k++; push(&S,x); on_stack[x] = 1; List list = neighbors(G, x); int j; for (j = 1; j <= list.size;j++){ int y = element_at(&list, j); if(num[y] < 0){ strong_connect(G,y); min_num[x] = min(min_num[x],min_num[y]); }else if (on_stack[y]) min_num[x] = min(min_num[x],num[y]); } if(num[x]==min_num[x]) { int w; do { w=top(&S); pop(&S); on_stack[w]=0; count++; }while(w!=x); } return count; } int strong(Graph *G) { int j, kq; // duyet toan bo do thi make_null_stack(&S); for(j=1;j<=G->n;j++) { num[j]=-1; on_stack[j]=0; } k=1; for(j=1;j<=G->n;j++) if(num[j]==-1) kq = strong_connect(G,j); return kq; } int main() { Graph G; int j,x,y,m,n; scanf("%d%d",&n,&m); init_graph(&G,n); for(j=1;j<=m;j++) { scanf("%d%d",&x,&y); add_edge(&G,x,y); } if(strong(&G) == n) // neu strong == so dinh thi strong connect printf("strong connected"); else printf("unconnected"); return 0; }

Be the first to comment

You can use [html][/html], [css][/css], [php][/php] and more to embed the code. Urls are automatically hyperlinked. Line breaks and paragraphs are automatically generated.