图论基础之 图中找环_图论找环

对于有向图而言 可以使用拓扑排序的方式找出图中的环

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int n;
int du[maxn];//入度
vector<int> gra[10];
vector<int> res;
void addedge(int a,int b){
    du[b]++;
    gra[a].push_back(b);
}
void topo(){
    queue<int> q;
    for(int i = 1; i <= n; i++){
        if(du[i] == 0){
            q.push(i);
        }
    }
    while(!q.empty()){
        int temp = q.front();
        q.pop();
        for(int i = 0; i < gra[temp].size(); i++){
            int to = gra[temp][i];
            du[to]--;
            if(!du[to]){
                q.push(i);
            }
        }
    }
}
int main(){
    cin>>n;
    for(int i = 0; i < n; i++){
        int a,b;
        cin>>a>>b;
        addedge(a,b);
    }
    topo();
    for(int i = 1; i <= n; i++){
        if(du[i]){
            cout<<i<<' ';
        }
    }
}

对于无向图 可以采用并查集的方式，在读边的时候，如果两个顶点在同一个集合中，说明构成了环，这时令这两个顶点作为起点和终点，深搜一下输出路径即可

蓝桥杯2017国赛c++b组 t4 找环

题意：

编号为1