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