#include #include #include #include #include #define N 500001 using namespace std; int n,m,fir[N],tot; bool v[N],u[N]; struct edge{int nxt,pnt;}e[N*2]; void ins(int a,int b) {tot++;e[tot].nxt=fir[a];e[tot].pnt=b;fir[a]=tot;} void dfs_tree(int x) //如果是树就直接dfs嘛，60分先拿到手 { printf("%d ",x);v[x]=1; priority_queue,greater > q; //小根堆存要跑的点 for(int i=fir[x];i;i=e[i].nxt) { int p=e[i].pnt; if(v[p]) continue; q.push(p); } while(!q.empty()) //从小到大拿出来 { dfs_tree(q.top()); q.pop(); } return; } int st; bool flag,tag; //flag表示是否已经找到了环，tag表示当前的点是否为环点 void search_circle(int x,int pre) //找环 { v[x]=1; for(int i=fir[x];i;i=e[i].nxt) { int p=e[i].pnt; if(p==pre) continue; if(!v[p]) { search_circle(p,x); if(flag) { u[x]=tag; if(x==st) tag=0; return; } } else {u[x]=1;flag=tag=1;st=p;return;} } return; } int another[N]; //玄学掉头another数组 void dfs_circle_tree(int x) //在基环树上奇技淫巧dfs { printf("%d ",x);v[x]=1; priority_queue,greater > q; for(int i=fir[x];i;i=e[i].nxt) { int p=e[i].pnt; if(v[p]) continue; q.push(p); } if(!u[x]||(x!=st&&u[x]&&flag==0)) //如果是非环点或者是已经拆过环了并且还不能是st { while(!q.empty()) { dfs_circle_tree(q.top()); q.pop(); } return; } else { if(x==st) //由此进入环中 { while(!q.empty()) { int p=q.top(); q.pop(); if(!u[p]) dfs_circle_tree(p); if(u[p]&&flag==0) { another[p]=q.top(); flag=1; dfs_circle_tree(p); continue; } if(u[p]&&flag==1) //如果进入环中后再一次回到st，并且开始跑另一个环点的时候，说明之前已经掉过头了，这个时候就可以取消标记然后当成树来对待。 {flag=0;if(!v[p]) dfs_circle_tree(p);} } return; } if(flag==1) //如果是第1遍跑环，这个时候是可以回头的 { while(!q.empty()) { int p=q.top(); q.pop(); if(!u[p]) dfs_circle_tree(p); else { if(!q.empty()) another[p]=q.top(); else another[p]=another[x]; if(p

题库

题库

900.[NOIP2018 提高组] 旅行

提交记录

测试用例