题解 P3916 【图的遍历】

这题有一个不用tarjan的做法，不知道是数据太弱还是我的做法本身就是对的 一开始写了一个把记录low数组改成记录能达到的最大编号 结果发现WA了，更新顺序不能保证是对的 然后我多更新了几次，直到任意节点的“最大编号”信息不再变化为止，然后就AC了 扔代码 ```cpp #include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MAXN=100010; struct edge { int v; edge *next; }*h[MAXN],pool[MAXN*2]; int top,changed; inline void addedge(int u,int v) { edge *tmp=&pool[top++];tmp->v=v;tmp->next=h[u];h[u]=tmp; } int vis[MAXN],hi[MAXN]; void search(int u) { vis[u]=1; for(edge *tmp=h[u];tmp;tmp=tmp->next) { if(!vis[tmp->v]) { search(tmp->v); } if(hi[tmp->v]>hi[u]) { changed=1;//这里也是关键 hi[u]=hi[tmp->v]; } } vis[u]=2; } int main() { int n,m,a,b; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++)hi[i]=i; for(int i=1;i<=m;i++) { scanf("%d%d",&a,&b); addedge(a,b); } //这里是关键 do { memset(vis,0,sizeof(vis));changed=0; for(int i=1;i<=n;i++) { if(!vis[i]) search(i); } }while(changed); //关键部分到此结束 for(int i=1;i<=n;i++) { printf("%d ",hi[i]); } printf("\n"); return 0; } ```