洛谷P3196C语言题解

根据题目最容易想到的肯定就是使用dfs进行解决

虽然知道可能会被时间复杂度卡，但是好像也没有其他方法了

最初的代码

#include<stdio.h>#include<stdlib.h>#include<string.h>typedef struct node
{int data;struct node*next;
}node;
int max=0;
node*nod[1000000];
int book[1000000];
void dfs(int x){if(x>max)max=x;node*tmp=nod[x]->next;while(tmp){if(!book[tmp->data]){book[tmp->data]=1;dfs(tmp->data);}tmp=tmp->next;}
}
int main(){int  n,m;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;}for(int i=0;i<m;i++){int x,y;scanf("%d%d",&x,&y);node*p=nod[x];while(p->next!=NULL&&p->next->data)p=p->next;node*tmp=(node*)malloc(sizeof(node));tmp->data=y;tmp->next=p->next;p->next=tmp;}for(int i=1;i<=n;i++){memset(book,0,sizeof(int)*100000);max=0;dfs(i);printf("%d ",max);}
}

如何解决：

如果我们每一次都是从要查的点出发，如果他和另外一个点最大能到达的点是一个，那么时间不是多花了一次嘛

如果我们知道这个点能被其余的点达到而且他还是最大的那一个点，势必会比赏面的dfs快

如何实现

为了实现上面的方法，我们要反向建边，这要我们才能知道大的点位可以到达哪些点位

同时，如果一个大的点位已经到过了一个点，那么后续较小的点位就没必要再从那个点位进行dfs（先前的大点dfs已经将从该点能到到达的点位包括他自己能到到达的最大点位更新为大的那个了）

#include<stdio.h>#include<string.h>#include<stdlib.h>typedef struct node
{int val;struct node*next;
}node;
node* nod[100001];
int maxn[100001];
int book[100001];
void dfs(int index,int ori){//查到了哪个点位，从哪个点开始查的if(book[index])return;book[index]=1;if(maxn[index]<ori)maxn[index]=ori;node*p=nod[index]->next;while(p){if(book[p->val]==0)dfs(p->val,ori);p=p->next;}return;
}
int main(){int n,m;scanf("%d%d",&n,&m);for(int i=1;i<=n;i++){nod[i]=(node*)malloc(sizeof(node));nod[i]->val=i;nod[i]->next=NULL;maxn[i]=i;}while(m--){int a,b;scanf("%d%d",&a,&b);node *p=(node*)malloc(sizeof(node));p->val=a;p->next=nod[b]->next;nod[b]->next=p;}for(int i=n;i>0;i--){if(nod[i]->next)dfs(nod[i]->val,i);}for(int i=1;i<=n;i++)printf("%d ",maxn[i]);
}