竞赛中找环有许多种问题，判断是否有环，找到环上的点，找到环上的边等等。
而只需要找到环上相邻的两点，或者环上的一条边就可以解决这三个问题。
有向图中，可以用拓扑排序的方法，把将拓扑排序完后限制条件仍未被清零的点即在环上的点。
#include
#define N 1000101
using namespace std;
int n, m, cnt, lin[N], deg[N];
struct edg {
int to, nex;
}e[N];
inline void add(int f, int t)
{
deg[t]++;
e[++cnt].nex = lin[f];
e[cnt].to = t;
lin[f] = cnt;
}
void topu()
{
queue
for (int i = 1; i <= n; i++)
if (!deg[i]) q.push(i);
while (!q.empty())
{
int cur = q.front(); q.pop();
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
deg[to]--;
if (!deg[to]) q.push(to);
}
}
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= m; i++)
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b);
}
topu();
for (int i = 1; i <= n; i++)
if (deg[i])
printf("%d ", i);
return 0;
}
无向图中，就不能用拓扑排序了，比较好的方法就是并查集。
并查集通过判断每一条边的两个端点是否在一个一个集合内来找到在同一个环上的两个边，然后以这两个点为起点和终点搜索，最终输出所有在他们路径上的点。
#include
#define N 1001011
using namespace std;
int n, m, cnt, fa[N], lin[N], vis[N], ha[N];
int find(int a)
{
if (fa[a] == a)
return a;
return fa[a] = find(fa[a]);
}
struct edg {
int to, nex, from;
}e[1001001];
inline void add(int f, int t )
{
e[++cnt].to = t;
e[cnt].from = f;
e[cnt].nex = lin[f];
lin[f] = cnt;
}
int dfs(int now, int end)
{
if (now == end) return 1;
int flag = 0;
for (int i = lin[now]; i; i = e[i].nex)
{
int to = e[i].to;
if (vis[to]) continue;
vis[to] = 1;
flag = max(flag, dfs(to, end));
if (flag) ha[now] = ha[to] = 1;
vis[to] = 0;
}
return flag;
}
int main()
{
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
fa[i] = i;
for (int i = 1, a, b; i <= n; i++)
{
scanf("%d%d", &a, &b);
add(a, b);
add(b, a);
int faa = find(a), fab = find(b);
memset(vis, 0, sizeof(vis));
if (faa == fab) //说明他们已经在同一个集合里
dfs(a, b);
fa[faa] = fab;
}
for (int i = 1; i <= n; i++)
if (ha[i])
printf("%d ", i);
return 0;
}
以上都是边权只有正的情况。
当然图论中也有判断负环和正环的情况（判断正环，负环一般不区别有向图、无向图）
负环：
如果一个点在求最短路松弛操作超过n次则说明至少有一个点更新了它两次，这说明一定出现了负环。
只需要用一个最短路算法即可判断是否出现负环，一般用\(spfa\)，因为\(Dijsktra\)不能用于存在负权边的图中。
正环：
可以将判负环的程序加边时边权取相反数，然后跑负环代码，也可以用求最长路的松弛操作（一定要将初始dis设为无穷小）（求最长路只能用spfa来松弛，dij松弛是错误的）如果原图中还是有负边权则还是不能用\(Dijsktra\)算法。
spfa据说可以用dfs/bfs但是dfs不稳定，dfs只需要通过是否扩展的节点在当前的栈中，就可以判断是否重复更新了。
bfs_spfa负环代码:
#include
#include
#include
#include
#include
#include
using namespace std;
struct edge
{
int from, to, len, nex;
} e[100100];
int cnt, lin[100010], b[100100], vis[100010], n, m, dis[100100];
bool flag;
inline void add(int u, int v, int l)
{
e[++cnt].from = u;
e[cnt].to = v;
e[cnt].nex = lin[u];
e[cnt].len = l;
lin[u] = cnt;
}
queue
int main()
{
int t;
scanf("%d", &t);
while (t--)
{
cnt = 0;
flag = 0;
memset(lin, 0, sizeof(lin));
memset(vis, 0, sizeof(vis));
memset(e,0,sizeof(e));
memset(b,0,sizeof(b));
scanf("%d%d", &n, &m);
for (int i = 1; i <= n; i++)
dis[i] = 2147483647;
for (int i = 1; i <= m; i++)
{
int a, b, c;
scanf("%d%d%d", &a, &b, &c);
if (c < 0) add(a, b, c);
else add(a, b, c), add(b, a, c);
}
q.push(1);
dis[1] = 0;
vis[1] = 1;
b[1] = 1;
while(!q.empty())
{
int cur = q.front();
q.pop();
b[cur] = 0;
if (vis[cur] >= n || vis[1] >= 2)//只要比n大则说明此出现了负环
{
flag = 1;
break;
}
for (int i = lin[cur]; i; i = e[i].nex)
{
int to = e[i].to;
if (dis[e[i].to] > dis[cur] + e[i].len)
{
dis[e[i].to] = dis[cur] + e[i].len;
if (!b[to])
{
vis[to]++;
q.push(to);
b[to] = 1;
}
}
}
}
while(!q.empty())q.pop();
if (flag) printf("YE5\n");
else printf("N0\n");
}
}