TONG HOP
unknown
plain_text
4 years ago
27 kB
6
Indexable
//Bài 1: Duyệt đồ thị //RONG #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Queue// typedef struct { int data[100]; int front, rear; } Queue; void make_null_queue(Queue* Q) { Q->front = 0; Q->rear = -1; } //Dua phan tu vap cuoi hang doi void push(Queue* Q, int x) { Q->rear++; Q->data[Q->rear] = x; } //Xem phan tu dau hang doi int top(Queue* Q) { return Q->data[Q->front]; } void pop(Queue* Q) { Q->front++; } int empty(Queue* Q) { return Q->front > Q->rear; } //BFS int mark[100]; void BFS_x(Graph *G, int s) { Queue Q; make_null_queue(&Q); push(&Q, s); while(!empty(&Q)) { int u=top(&Q); pop(&Q); if(mark[u]!=0) continue; printf("%d\n", u); mark[u]=1; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)) push(&Q,v); } } } void BFS(Graph *G) { int i; for(i=1; i<=G->n; i++) mark[i]=0; BFS_x(G, 1); for(i=1; i<=G->n; i++) if(mark[i]==0) { BFS_x(G, i); } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //int mark[100]; for(j=1; j<=G.n; j++) mark[j]=0; //print_graph(&G); BFS(&G); return 0; } //SAU #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Stack typedef struct { int data[100]; 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; } //DFS int mark[100]; void DFS_x(Graph *G, int s) { Stack S; make_null_stack(&S); push(&S, s); while(!empty(&S)) { int u=top(&S); pop(&S); if(mark[u]!=0) { continue; } printf("%d\n", u); mark[u]=1; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)) push(&S, v); } } } void DFS(Graph *G) { int i; for(i=1; i<=G->n; i++) mark[i]=0; DFS_x(G, 1); for(i=1; i<=G->n; i++) if(mark[i]==0) { DFS_x(G, i); } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //int mark[100]; for(j=1; j<=G.n; j++) mark[j]=0; //print_graph(&G); DFS(&G); return 0; } //DEQUY-vohuong #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //DFS int mark[100]; void DQ_x(Graph *G, int s) { if(mark[s]) return ; printf("%d\n", s); mark[s]=1; int v; for(v=1; v<=G->n; v++) if(adjecent(G, s, v)) DQ_x(G, v); } void DQ(Graph *G) { int i; for(i=1; i<=G->n; i++) mark[i]=0; DQ_x(G, 1); for(i=1; i<=G->n; i++) if(mark[i]==0) { DQ_x(G, i); } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //int mark[100]; for(j=1; j<=G.n; j++) mark[j]=0; //print_graph(&G); DQ(&G); return 0; } //DUNG CAY-RONG #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Queue typedef struct { int u, p; }ElementType; typedef struct { ElementType data[100]; int front, rear; } Queue; void make_null_queue(Queue* Q) { Q->front = 0; Q->rear = -1; } //Dua phan tu vap cuoi hang doi = enqueue void push(Queue* Q, ElementType pair) { Q->rear++; Q->data[Q->rear].u = pair.u; Q->data[Q->rear].p = pair.p; } //Xem phan tu dau hang doi = front ElementType top(Queue* Q) { return Q->data[Q->front]; } //dequeue xóa ph?n tu dau hang doi void pop(Queue* Q) { Q->front++; } int empty(Queue* Q) { return Q->front > Q->rear; } //BFS int mark[100]; int parent[100]; void BFS_x(Graph *G, int s) { Queue Q; make_null_queue(&Q); ElementType pair; pair.u=s; pair.p=0; push(&Q, pair); while(!empty(&Q)) { ElementType pair=top(&Q); pop(&Q); int u=pair.u, p=pair.p; if(mark[u]!=0) continue; // printf("%d %d\n", u, parent[s]); mark[u]=1; parent[u]=p; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)) { ElementType pair; pair.u=v; pair.p=u; push(&Q, pair); } } } } void BFS(Graph *G) { int i; for(i=1; i<=G->n; i++) mark[i]=0; BFS_x(G, 1); for(i=1; i<=G->n; i++) if(mark[i]==0) { BFS_x(G, i); } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //int mark[100]; for(j=1; j<=G.n; j++) mark[j]=0; //print_graph(&G); BFS(&G); for(i = 1;i<=n;i++){ printf("%d %d\n",i,parent[i]); } return 0; } //DUNG CAY_SAU #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Stack typedef struct { int u, p; }ElementType; typedef struct { ElementType data[100]; int size; } Stack; void make_null_stack(Stack* S) { S->size = 0; } void push(Stack* S, ElementType pair) { S->data[S->size].u = pair.u; S->data[S->size].p = pair.p; S->size++; } ElementType top(Stack* S) { return S->data[S->size-1]; } void pop(Stack* S) { S->size--; } int empty(Stack* S) { return S->size == 0; } //BFS int mark[100]; int parent[100]; void DFS_x(Graph *G, int s) { Stack S; make_null_stack(&S); ElementType pair; pair.u=s; pair.p=0; push(&S, pair); while(!empty(&S)) { ElementType pair=top(&S); pop(&S); int u=pair.u, p=pair.p; if(mark[u]!=0) { continue; } mark[u]=1; parent[u]=p; //printf("%d %d\n", u, parent[u]); int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)){ ElementType pair; pair.u=v; pair.p=u; push(&S, pair); } } } } void DFS(Graph *G) { int i; for(i=1; i<=G->n; i++) mark[i]=0; DFS_x(G, 1); for(i=1; i<=G->n; i++) if(mark[i]==0) { DFS_x(G, i); } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } for(j=1; j<=G.n; j++) mark[j]=0; //print_graph(&G); DFS(&G); for(i = 1;i<=n;i++){ printf("%d %d\n",i,parent[i]); } return 0; } //DUNG CAY_DEQUY #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Stack typedef struct { int u, p; }ElementType; typedef struct { ElementType data[100]; int size; } Stack; void make_null_stack(Stack* S) { S->size = 0; } void push(Stack* S, ElementType pair) { S->data[S->size].u = pair.u; S->data[S->size].p = pair.p; S->size++; } ElementType top(Stack* S) { return S->data[S->size-1]; } void pop(Stack* S) { S->size--; } int empty(Stack* S) { return S->size == 0; } //BFS int mark[100]; int parent[100]; void DFS_x(Graph *G, int u, int p) { // Stack S; // make_null_stack(&S); // // ElementType pair; // pair.u=s; pair.p=0; // push(&S, pair); // // while(!empty(&S)) { // ElementType pair=top(&S); pop(&S); // int u=pair.u, p=pair.p; // if(mark[u]!=0) { // continue; // } // // mark[u]=1; // parent[u]=p; // printf("%d %d\n", u, parent[u]); // int v; // for(v=1; v<=G->n; v++) { // if(adjecent(G, u, v)){ // ElementType pair; // pair.u=v; pair.p=u; // push(&S, pair); // } // } // } if(mark[u] != 0) return; mark[u]=1; parent[u]=p; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v) && mark[v]==0) { DFS_x(G, v, u); } } } void DFS(Graph *G) { int i; for(i=1; i<=G->n; i++) mark[i]=0; DFS_x(G, 1, 0); for(i=1; i<=G->n; i++) if(mark[i]==0) { DFS_x(G, i, 0); } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } for(j=1; j<=G.n; j++) mark[j]=0; //print_graph(&G); DFS(&G); for(i = 1;i<=n;i++){ printf("%d %d\n",i,parent[i]); } return 0; } //CHUA DAO #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Queue// typedef struct { int data[100]; int front, rear; } Queue; void make_null_queue(Queue* Q) { Q->front = 0; Q->rear = -1; } //Dua phan tu vap cuoi hang doi void push(Queue* Q, int x) { Q->rear++; Q->data[Q->rear] = x; } //Xem phan tu dau hang doi int top(Queue* Q) { return Q->data[Q->front]; } void pop(Queue* Q) { Q->front++; } int empty(Queue* Q) { return Q->front > Q->rear; } //BFS int mark[100]; void BFS_x(Graph *G, int s) { Queue Q; make_null_queue(&Q); push(&Q, s); while(!empty(&Q)) { int u=top(&Q); pop(&Q); if(mark[u]!=0) continue; // printf("%d\n", u); mark[u]=1; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)) push(&Q,v); } } } int connected(Graph *pG) { int u; for(u=1; u<=pG->n; u++) mark[u]=0; BFS_x(pG, 1); for(u=1; u<=pG->n; u++) if(mark[u]==0) return 0; return 1; } int main() { //freopen("dt.txt", "r", stdin); int i, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } int check = connected(&G); if(check) printf("YES"); else printf("NO"); } //TAY DU KY #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Queue// typedef struct { int data[100]; int front, rear; } Queue; void make_null_queue(Queue* Q) { Q->front = 0; Q->rear = -1; } //Dua phan tu vap cuoi hang doi void push(Queue* Q, int x) { Q->rear++; Q->data[Q->rear] = x; } //Xem phan tu dau hang doi int top(Queue* Q) { return Q->data[Q->front]; } void pop(Queue* Q) { Q->front++; } int empty(Queue* Q) { return Q->front > Q->rear; } //BFS int mark[100]; void BFS_x(Graph *G, int s) { Queue Q; make_null_queue(&Q); push(&Q, s); while(!empty(&Q)) { int u=top(&Q); pop(&Q); if(mark[u]!=0) continue; // printf("%d\n", u); mark[u]=1; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)) push(&Q,v); } } } int connected(Graph *pG) { int u; for(u=1; u<=pG->n; u++) mark[u]=0; BFS_x(pG, 1); for(u=1; u<=pG->n; u++) if(mark[u]==0) return 0; return 1; } int main() { //freopen("dt.txt", "r", stdin); int i, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } int check = connected(&G); if(check) printf("DUOC"); else printf("KHONG"); } //CHUA CHU TRINH KHONG #include<stdio.h> typedef struct{ int n,m; int A[100][100]; }Graph; void initG(Graph *G, int n){ G->n=n; int i,j; for(i=1;i<=G->n;i++){ for(j=1;j<=n;j++){ G->A[i][j]=0; } } } void addedge(Graph *G, int x, int y){ if(x!=y){ G->A[x][y]=1; G->A[y][x]=1; } else G->A[x][x]+=2; } typedef struct{ int size; int L[100]; }List; void makenullL(List *L){ L->size=0; } void pushL(List *L, int x){ L->L[L->size]=x; L->size++; } typedef struct{ int S[100]; int size; }Stack; void makenullS(Stack *S){ S->size=0; } int topS(Stack *S){ return S->S[S->size-1]; } void popS(Stack *S){ S->size--; } void pushS(Stack *S, int x){ S->S[S->size]=x; S->size++; } int emptyS(Stack *S){ return S->size==0; } void inMT(Graph *G){ int i,j; for(i=1;i<=G->n;i++){ printf("%d ",i); for(j=1;j<=G->n;j++){ printf("%d ",G->A[i][j]); } printf("\n"); } } List neighbour(Graph *G,int x){ List L; makenullL(&L); int i; for(i=0;i<=G->n;i++){ if(G->A[x][i]==1 ) pushL(&L,i); } return L; } int color[100],cycle; #define while 0 #define black 1 #define gray 2 void dfs(Graph *G,int x,int par){ color[x]=gray; int j; List L=neighbour(G,x); for(j=1;j<=L.size;j++){ int y=L.L[j-1]; if(y==par)continue; if(color[y]==gray){ cycle=1; return; } if(color[y]==while)dfs(G,y,x); } color[x]=black; } int contains(Graph *G){ int i; for(i=1;i<=G->n;i++){ color[i]=while; } cycle=0; for(i=1;i<=G->n;i++){ if(color[i]==while) dfs(G,i,0); } return cycle; } int main(){ Graph G; int n, m, u, v, e; scanf("%d%d", &n, &m); initG(&G, n); for (e = 0; e < m; e++) { scanf("%d %d", &u, &v); addedge(&G, u, v); } if(contains(&G)==0)printf("NO"); else printf("YES"); return 0; } //CHUA CHU TRINH KHONG, CO KHUYEN #include<stdio.h> typedef struct{ int n,m; int A[100][100]; }Graph; void initG(Graph *G, int n){ G->n=n; int i,j; for(i=1;i<=G->n;i++){ for(j=1;j<=n;j++){ G->A[i][j]=0; } } } void addedge(Graph *G, int x, int y){ if(x!=y){ G->A[x][y]++; G->A[y][x]++; } else G->A[x][x]+=2; } typedef struct{ int size; int L[100]; }List; void makenullL(List *L){ L->size=0; } void pushL(List *L, int x){ L->L[L->size]=x; L->size++; } typedef struct{ int S[100]; int size; }Stack; void makenullS(Stack *S){ S->size=0; } int topS(Stack *S){ return S->S[S->size-1]; } void popS(Stack *S){ S->size--; } void pushS(Stack *S, int x){ S->S[S->size]=x; S->size++; } int emptyS(Stack *S){ return S->size==0; } void inMT(Graph *G){ int i,j; for(i=1;i<=G->n;i++){ for(j=1;j<=G->n;j++){ printf("%d ",G->A[i][j]); } printf("\n"); } } List neighbour(Graph *G,int x){ List L; makenullL(&L); int i,j; for(i=0;i<=G->n;i++){ for(j=1;j<=G->A[x][i];j++){ pushL(&L,i); } } return L; } 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->L[i]==L->L[j]) tmp=1; } } return tmp; } int color[100],cycle; #define while 0 #define black 1 #define gray 2 void dfs(Graph *G,int x,int par){ color[x]=gray; int j; List L=neighbour(G,x); if(KTtrungL(&L)==1){ cycle=1; return; } for(j=1;j<=L.size;j++){ int y=L.L[j-1]; if(y==par)continue; if(color[y]==gray){ cycle=1; return; } if(color[y]==while)dfs(G,y,x); } color[x]=black; } int contains(Graph *G){ int i; for(i=1;i<=G->n;i++){ color[i]=while; } cycle=0; for(i=1;i<=G->n;i++){ if(color[i]==while) dfs(G,i,0); } return cycle; } int main(){ Graph G; int n, m, u, v, e; scanf("%d%d", &n, &m); initG(&G, n); for (e = 0; e < m; e++) { scanf("%d %d", &u, &v); addedge(&G, u, v); } // inMT(&G); if(contains(&G)==0)printf("NO"); else printf("YES"); return 0; } //HADDOCK #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } //Stack typedef struct { int data[100]; 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; } //DFS #define WHITE 0 #define GRAY 1 #define BLACK 2 int color[100]; int has_circle; void DFS_x(Graph *G, int s) { color[s]=GRAY; int v; for(v=1; v<=G->n; v++) if(adjecent(G, s, v)) { if(color[v]==WHITE) DFS_x(G, v); else if(color[v]==GRAY) has_circle=1; } color[s]=BLACK; } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } for(i=0; i<=G.n; i++) { color[u]=WHITE; } has_circle=0; for(j=0; j<=G.n; j++) if(color[j]==WHITE) DFS_x(&G, j); if(has_circle) printf("NO"); else printf("YES"); return 0; } //CHIA DOI BONG #include<stdio.h> #define NOCO 0 #define BLUE 1 #define RED 2 //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; pG->A[y][x]=1; } //Kiem tra lang gieng x, y phai lang gieng khong? int adjecent(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"); } } int color[100]; int conflict; //int B[100]; void colorize(Graph *G, int u, int c) { color[u]=c; int v; for(v=1; v<=G->n; v++) { if(adjecent(G, u, v)) { if(color[v]==NOCO) colorize(G, v, 3-c); else if(color[v]==color[u]) conflict=1; } } } int main() { //freopen("dt.txt", "r", stdin); int i, j, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=1; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //print_graph(&G); for(i=1; i<=G.n; i++) { color[u]=NOCO; } conflict=0; for(j=1; j<=G.n; j++) if(color[j]==NOCO) colorize(&G, j, 1); //printf("%d", color[1]); if(conflict!=1){ for(i=1; i<=n; i++) { if(color[i]==BLUE) printf("%d ", i); } printf("\n"); for(i=1; i<=n; i++) { if(color[i]==RED) printf("%d ", i); } } else printf("IMPOSSIBLE"); return 0; } //LIEN THONG MANH KHONG? #include<stdio.h> //Stack typedef struct { int data[100]; 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; } //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; } int adjecent(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"); } } int num[100], min_num[100]; int k; Stack S; int on_stack[100]; int mark[100]; int min(int a, int b) { if(a<b) return a; if(a==b) return 0; else return b; } int check=0; void SCC(Graph *pG, int u) { num[u]=min_num[u]=k; k++; push(&S, u); on_stack[u]=1; int v; for(v=1; v<=pG->n; v++) { if(adjecent(pG, u, v)) { if(num[v]<0) { SCC(pG, v); min_num[u]=min(min_num[u], min_num[v]); } else if(on_stack[v]) min_num[u]=min(min_num[u], num[v]); } } if(num[u]==min_num[u]) { //printf("LTM, dinh %d la dinh khop \n", u); //check=1; check++; int w; do{ w=top(&S); pop(&S); on_stack[w]=0; } while(w!=u); } } int connected(Graph *pG) { int u; for(u=1; u<=pG->n; u++) { num[u]=0; on_stack[u]=0; } make_null_stack(&S); for(u=1; u<=pG->n; u++) if(num[u]==0) SCC(pG, u); return check; } int main() { //freopen("dt.txt", "r", stdin); int i, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //print_graph(&G); for(i=1; i<=G.n; i++) num[i]=-1; k=1; make_null_stack(&S); for(i=1; i<G.n; i++) if(num[i]==-1) SCC(&G, i); //printf("%d\n",check ); if(check==1) printf("unconnected"); else printf("strong connected"); return 0; } //DEM BO PHAN LTM #include<stdio.h> //Stack typedef struct { int data[100]; 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; } //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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) { pG->A[x][y]=1; } int adjecent(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"); } } int num[100], min_num[100]; int k; Stack S; int on_stack[100]; int mark[100]; int min(int a, int b) { if(a<b) return a; if(a==b) return 0; else return b; } int check=0; void SCC(Graph *pG, int u) { num[u]=min_num[u]=k; k++; push(&S, u); on_stack[u]=1; int v; for(v=1; v<=pG->n; v++) { if(adjecent(pG, u, v)) { if(num[v]<0) { SCC(pG, v); min_num[u]=min(min_num[u], min_num[v]); } else if(on_stack[v]) min_num[u]=min(min_num[u], num[v]); } } if(num[u]==min_num[u]) { //printf("LTM, dinh %d la dinh khop \n", u); //check=1; check++; int w; do{ w=top(&S); pop(&S); on_stack[w]=0; } while(w!=u); } } int connected(Graph *pG) { int u; for(u=1; u<=pG->n; u++) { num[u]=-1; on_stack[u]=0; } make_null_stack(&S); for(u=1; u<=pG->n; u++) if(num[u]==-1) SCC(pG, u); return check; } int main() { //freopen("dt1.txt", "r", stdin); int i, m, n, u, v; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d", &u, &v); add_edge(&G, u, v); } //print_graph(&G); for(i=1; i<=G.n; i++) num[i]=-1; k=1; make_null_stack(&S); for(i=1; i<=G.n; i++) if(num[i]==-1) SCC(&G, i); printf("%d",connected(&G)+1); return 0; } //COME AND GO #include<stdio.h> //Graph typedef struct { int A[20][20]; int n; //So luong dinh }Graph; void init_graph(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, int e) { if(e==1) pG->A[x][y]=1; else if(e==2) { pG->A[x][y]=1; pG->A[y][x]=1; } } int adjecent(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"); } } //Stack typedef struct { int data[100]; 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; } int min(int x,int y){ return x<y ? x:y; } int check; int num[100], min_num[100]; int k; Stack S; int on_stack[100]; void SCC(Graph *pG, int u) { num[u]=min_num[u]=k; k++; push(&S, u); on_stack[u]=1; int v; for(v=1; v<=pG->n; v++) { if(adjecent(pG, u, v)) { if(num[v]<0) { SCC(pG, v); min_num[u]=min(min_num[u], min_num[v]); } else if(on_stack[v]) min_num[u]=min(min_num[u], num[v]); } } if(num[u]==min_num[u]) { // printf("LTM, dinh %d la dinh khop \n", u); check++; int w; do{ w=top(&S); pop(&S); on_stack[w]=0; } while(w!=u); } } int connected(Graph *pG) { int u; for(u=1; u<=pG->n; u++) { num[u]=0; on_stack[u]=0; } make_null_stack(&S); for(u=1; u<=pG->n; u++) if(num[u]==0) SCC(pG, u); return check; } int main() { //freopen("dt3.txt", "r", stdin); int i, m, n, u, v, e; Graph G; scanf("%d%d", &n, &m); init_graph(&G, n); for(i=0; i<=m; i++) { scanf("%d%d%d", &u, &v, &e); add_edge(&G, u, v, e); } //print_graph(&G); for(i=1; i<=G.n; i++) num[i]=-1; k=1; make_null_stack(&S); for(i=1; i<=G.n; i++) if(num[i]==-1) SCC(&G, i); //printf("%d\n",check); if(check==1) printf("OKIE"); else printf("NO"); return 0; }
Editor is loading...