基环树找环-模板

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 1000010
#define MAXM 5010
inline int read()
{
int x = 0,ff = 1;char ch = getchar();
while(!isdigit(ch))
{
if(ch == '-') ff = -1;
ch = getchar();
}
while(isdigit(ch))
{
x = (x << 1) + (x << 3) + (ch ^ 48);
ch = getchar();
}
return x * ff;
}
inline void write(int x)
{
if(x < 0) putchar('-'),x = -x;
if(x > 9) write(x / 10);
putchar(x % 10 + '0');
}
int a,ti = 0,cnt = 0,fa[MAXN],vis[MAXN],loop[MAXN];
int lin[MAXN],tot = 0;
struct edge
{
int y,v,next;
}e[MAXN];
inline void add(int xx,int yy,int vv)
{
e[++tot].y = yy;
e[tot].v = vv;
e[tot].next = lin[xx];
lin[xx] = tot;
}
void get_loop(int x)
{
vis[x] = ++ti;
for(int i = lin[x],y;i;i = e[i].next)
{
if((y = e[i].y) == fa[x]) continue;
if(vis[y])
{
if(vis[y] < vis[x]) continue;
loop[++cnt] = y;
for(y = fa[y];y != fa[x];y = fa[y])
loop[++cnt] = y;
}
else fa[y] = x,get_loop(y);
}
}
int main()
{
a = read();
for(int i = 1;i <= a;++i)
{
int y,v;
y = read(); v = read();
add(i,y,v);
add(y,i,v);
}
get_loop(1);
for(int i = 1;i <= cnt;++i)
write(loop[i]),putchar(' ');
return 0;
}