洛谷5318C语言题解
这道题一开始想直接使用邻接矩阵解决
BUT：
如果你要建立一个二维数组，内存就爆了
SO——邻接表
为什么邻接表能行？
-
空间利用率更高
-
构建也方便
构建时需要注意： 这里相当于是一个有向图而不是无向图
就拿题目中的样例来说
进行dfs，如果你是按照无向图进行构建的话
输出的结果回事12563748
而题目中要的是12563784
当然book函数进行记录也是必不可少的（毕竟是图而不是树）
#include<stdio.h>#include<stdlib.h>int n,m;
typedef struct node{int data;struct node*next;
}node;
node*nod[100010];
int book[100010];
void insertedge(int x,int y){node*p=(node*)malloc(sizeof(node));p->data=y;node*tmp=nod[x];while(tmp->next&&tmp->next->data<y){tmp=tmp->next;}p->next=tmp->next;tmp->next=p;
}void dfs(int index){if(index>n)return ;printf("%d ",nod[index]->data);book[index]=1;node*p=nod[index]->next;while(p!=NULL){if(!book[p->data]){dfs(p->data);book[p->data]=1;}p=p->next;}}void bfs(){int que[100000];int book1[100010]={0};int head,tail;head=tail=1;que[tail]=nod[1]->data;book1[nod[1]->data]=1;tail++;while(head<tail){printf("%d ",que[head]);node*p=nod[que[head]]->next;while(p){if(book1[p->data]==0){que[tail++]=p->data;book1[p->data]=1;}p=p->next;}head++;}}
int main(){scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){nod[i]=(node*)malloc(sizeof(node));nod[i]->data=i;nod[i]->next=NULL;}while(m--){int x,y;scanf("%d%d",&x,&y);insertedge(x,y);}dfs(1);printf("\n");bfs();}