Untitled

mail@pastecode.io avatar
unknown
c_cpp
2 years ago
1.9 kB
3
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;
}

//Hang doi
typedef struct {
	int data[MAX_ELEMENTS];
	int size;
} Stack;

void make_null_S(Stack *S) {
	S->size=0;
}

void push_S(Stack *S, int x) {
	S->data[S->size] = x;
	S->size++;
}

int top_S(Stack *S) {
	return S->data[S->size-1];
}

void pop_S(Stack *S) {
	S->size--;
}

int empty_S(Stack *S) {
	return S->size=0;
}

int mark[100];

void DFS(Graph *G, int x) {
	Stack S;
	make_null_S(&S);
	push_S(&S,x);
	while (!empty_S(&S)) {
		int u=top_S(&S); pop_S(&S);
		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_S(&S,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)
			DFS(&G,i);
	return 0;
}