Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.9 kB
0
Indexable
Never
#include <stdio.h>

#define MAX_ELEMENTS 100
#define MAX_VERTICES 100

//Ma tran ke
typedef struct {
	int n;
	int A[MAX_VERTICES][MAX_VERTICES];
} Graph;

void init_G(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;
}

void add_edge(Graph *G, int x, int y) {
	G->A[x][y]=1;
	G->A[y][x]=1;
}

int adjacent(Graph *G, int x, int y) {
	return G->A[x][y];
}

//List
typedef struct {
	int data[MAX_ELEMENTS];
	int size;
} List;

void make_null_L (List *L) {
	L->size=0;
}

void push_back_L (List *L, int x) {
	L->data[L->size] = x;
	L->size++;
}

int elementat_L(List *L, int i) {
	return(L->data[i-1]);
}

List neighbors(Graph *G, int x) {
	//Graph G;
	int y;
	List L;
	make_null_L(&L);
	for(y=1;y<=G->n;y++)
		if(adjacent(G,x,y)==1)
			push_back_L(&L, y);
	return L;
}

//Ngan xep
typedef struct {
	int data[MAX_ELEMENTS];
	int front, rear;
} Queue;

void make_null_Q(Queue *Q) {
	Q->front = 0;
	Q->rear = -1;
}

void push_Q(Queue *Q, int x) {
	Q->rear++;
	Q->data[Q->rear] = x;
}

int top_Q(Queue *Q) {
	return Q->data[Q->front];
}

void pop_Q(Queue *Q) {
	Q->front++;
}

int empty_Q(Queue *Q) {
	return Q->front > Q->rear;
}

int mark[100];

void BFS(Graph *G, int x) {
	Queue Q;
	make_null_Q(&Q);
	push_Q(&Q,x);
	while (!empty_Q(&Q)) {
		int u=top_Q(&Q); pop_Q(&Q);
		if (mark[u]!=0) continue;
			printf("%d\n",u);
		mark[u]=1;
		int i;
		for (i=1;i<=G->n;i++){
			if (adjacent(G,u,i))
				push_Q(&Q,i);
		}
	}
}

int main() {
	freopen("dt.txt", "r", stdin); //Chay tren else nho bo dong nay
	Graph G;
	int n, m, u, v, e;
	scanf("%d%d", &n, &m);
	init_G(&G, n);
	
	for (e = 0; e < m; e++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
	
	int i;
	for (i=1;i<=G.n;i++)
		mark[i]=0;
	for (i=1;i<=G.n;i++)
		if (mark[i]==0)
			BFS(&G,i);
	return 0;
}