微网站自助建设,响应式网站模板企业,35互联做网站怎么样,如何破解网站后台好水啊#xff0c;那我来水一篇题解。
题目就是要你在树上找环。那么我们想#xff0c;怎么知道出现了环#xff1f;
首先明确一点#xff0c;在一棵树上#xff0c;任意两点有且只有一条路径使它们相连。所以当我们发现原本就相连的点又要再连一次就知道出现了环。
是…好水啊那我来水一篇题解。
题目就是要你在树上找环。那么我们想怎么知道出现了环
首先明确一点在一棵树上任意两点有且只有一条路径使它们相连。所以当我们发现原本就相连的点又要再连一次就知道出现了环。
是不是很像最小生成树里面的 Kurskal 算法其实 Kruskal 的原理就是用并查集来判断两点是否联通不连通就连一条边。和找环其实是一样的。 #includebits/stdc.h
using namespace std;
const int N2e65;
int v[N],nxt[N],fst[N],idx;
int vis[N],fa[N],loop[N],cnt,num1;
int n,x,y;
void add(int a,int b){v[idx]b;nxt[idx]fst[a];fst[a]idx;
}
void get_loop(int x){vis[x]num;for(int ifst[x];~i;inxt[i]){int yv[i];if(yfa[x]) continue;if(vis[y]){if(vis[y]vis[x]) continue;loop[cnt]y;for(;y!x;yfa[y]){loop[cnt]fa[y];}}else{fa[y]x;get_loop(y);}}
}
int main(){cinn;memset(fst,-1,sizeof(fst));for(int i1;in;i){scanf(%d%d,x,y); add(x,y);add(y,x);}get_loop(1);sort(loop1,loopcnt1);for(int i1;icnt;i) printf(%d ,loop[i]);return 0;
}
