#include #include #include const int MAXV=50; typedef struct _edgeNode { int adj; int w; _edgeNode *next; } EdgeNode; typedef struct _VertexNode{ char data[10]; EdgeNode *head; }VertexNode; typedef struct { VertexNode vertex[MAXV]; int vn, en; }AdjList; int LocateVertex(AdjList *G, char v[10]) { int i; for(i=0;ivn;i++) if(strcmp(G->vertex[i].data,v)==0) return i; return -1; } void InitGraph(AdjList *G) { G->vn=0;G->en=0; } void CreateAdjList(AdjList *G) { int i,j,k; EdgeNode *s; char ic[10], jc[10]; int w; scanf("%d %d", &G->vn, &G->en); for(i=0;ivn;i++) { scanf("%s", G->vertex[i].data); G->vertex[i].head=NULL; } for(k=0; ken;k++) { scanf("%s %s %d",&ic, &jc, &w); i=LocateVertex(G,ic); if(i<0) return; j=LocateVertex(G,jc); if(j<0) return; s=(EdgeNode *)malloc(sizeof(EdgeNode)); s->adj=j; s->w=w; s->next=G->vertex[i].head; G->vertex[i].head=s; } } void Output(AdjList *G) { printf("%d %d\n",G->vn, G->en); for(int i=0;ivn;i++) if(ivn-1) printf("%s ",G->vertex[i].data); else printf("%s\n",G->vertex[i].data); for(int i=0;ivn;i++) { EdgeNode *p=G->vertex[i].head; while(p) { printf("(%s %s %d)",G->vertex[i].data, G->vertex[p->adj].data,p->w); p=p->next; } if(G->vertex[i].head) printf("\n"); } } int delEdge(AdjList *G, char v1[], char v2[]) { int vi=LocateVertex(G,v1); int vj=LocateVertex(G,v2); EdgeNode *q; if(vi<0 || vj<0) return 0; EdgeNode *p=G->vertex[vi].head; if(p->adj==vj) { q=p; G->vertex[vi].head=p->next; free(q); G->en--; return 1; } EdgeNode *pre=p; p=p->next; while(p && p->adj !=vj) { pre=p; p=p->next; } if(p) { q=p; pre->next=p->next; free(q); G->en--; } return 1; } int visited[MAXV]; int DFS(AdjList *G, int v0, int v2) { EdgeNode *p; int w; if(v0==v2) return 1; visited[v0]=1; p=G->vertex[v0].head; while(p!=NULL) { w=p->adj; if(!visited[w]) { if(w==v2 || DFS(G,w,v2)==1) return 1; } p=p->next; } return 0; } int connect(AdjList *g, char v1[], char v2[]) { int vi = LocateVertex(g,v1); int vj=LocateVertex(g,v2); if(vi<0 || vj<0) return 0; for(int i=0;ivn;i++) visited[i]=0; if(DFS(g,vi,vj)==1) return 1; else return 0; } int main() { AdjList G; InitGraph(&G); CreateAdjList(&G); char v1[10], v2[10]; scanf("%s %s",v1,v2); printf("%d\n",connect(&G,v1,v2)); return 0; }

Determine connectivity of two vertex in DG