#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.