Untitled

 avatar
unknown
c_cpp
4 years ago
2.5 kB
4
Indexable
#include<stdio.h>

//Graph
typedef struct {
	int A[20][20];
	int n; //So luong dinh
}Graph;

void init_G(Graph *pG, int n) {
	int i, j;
	pG->n=n;
	for(i=1; i<=n; i++) {
		for(j=1; j<=n; j++)
			pG->A[i][j]=0;	
	}
}

void add_edge(Graph *pG, int x, int y) {
	if(x!=y) {
		pG->A[x][y]++;
		pG->A[y][x]++;
	}
	else pG->A[x][x]+=2;
	
}

//Kiem tra lang gieng x, y phai lang gieng khong?
int adjacent(Graph *pG, int x, int y) {
	return pG->A[x][y];
}

void print_graph(Graph *pG) {
	int i, j;
	for(i=1; i<=pG->n; i++) {
		for(j=1; j<=pG->n; j++) 
			printf("%d ", pG->A[i][j]);
		printf("\n");
	}
}

//List
typedef struct {
	int data[100];
	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) {
	int i,j;
	List L;
	make_null_L(&L);
	for(i=0;i<=G->n;i++)
		for(j=1;j<=G->A[x][i];j++)
			push_back_L(&L, i);
	return L;
}

//Stack
typedef struct {
	int data[100];
	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 KTTrungL(List *L) {
	int i,j,tmp=0;
	for(i=0;i<=L->size-1;i++) 
		for(j=i+1;j<=L->size;j++)
			if(L->data[i] == L->data[j]) 
				tmp=1;
	return tmp;
}

#define WHITE 0
#define GRAY 2
#define BLACK 1

//DFS
int color[100];
int has_circle;

void DFS(Graph *G, int x, int p) {
	color[x]=GRAY;
	int i;
	List L = neighbors(G,x);
	if (KTTrungL(&L)==1) {
		has_circle=1;
		return;
	}

	for(i=1;i<=L.size;i++) {
		int y=L.data[i-1];
		if (y==p) continue;
		if (color[y]==WHITE)
			DFS(G,y,x);
		if (color[y]==GRAY) {
			has_circle=1;
			return;
		}
	}
	color[x] = BLACK;
}

int contains(Graph *G){
	int i;
	for(i=1;i<=G->n;i++){
		color[i]=WHITE;
	}
	has_circle=0;
	for(i=1;i<=G->n;i++){
		if(color[i]==WHITE) DFS(G,i,0);
	}
	return has_circle;
}	

int main() {
	freopen("dt.txt", "r", stdin);
	int i, m, n, u, v;
	Graph G;	
	scanf("%d%d", &n, &m);
	init_G(&G, n);
	
	for(i=0; i<=m; i++) {
		scanf("%d%d", &u, &v);
		add_edge(&G, u, v);
	}
		
	if(contains(&G)==0) printf("NO");
		else printf("YES");
	return 0;
}
Editor is loading...