Jiez19971225‘s Blog

做自己爱做的事

0%

图论基础之图中找环

发表于 更新于 分类于   |   字数统计: 1.3k(字)   |   阅读时长: 6(分)

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
#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 到 n 的 n 个点，以及 n-1 条边构成一棵树。现在在树上加上一条边，这样就构成了一个含环的图了。请你找出该环上的结点，从小到大输出这些结点编号。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e+7;
int n;
int p[maxn];
vector<int> gra[10];
vector<int> res;
int init(){
    memset(p,0,sizeof(p));
    for(int i = 1; i <= n; i++){
        p[i] = i;
    }
}
int find(int x){
    return p[x]==x?x:p[x]=find(p[x]);
}
int unit(int x,int y){
    p[x] = y;
}
void addedge(int x,int y){
    gra[x].push_back(y);
    gra[y].push_back(x);
}
int s,e;
int vis[maxn];
int path[maxn];
void dfs(int x){
    cout<<x<<endl;
    for(int i = 0; i < gra[x].size(); i++){
        int to = gra[x][i];
        if(!vis[to]){
            path[to] = x;// 记录路径
            vis[to] = 1;
            if(to == e){
                return;
            }
            dfs(to);
        }
    }
}
int main(){
    freopen("in.txt","r",stdin);
    cin>>n;
    init();
    memset(vis,0,sizeof(vis));
    memset(path,0,sizeof(path));
    for(int i = 0; i < n; i++){
        int a,b;
        cin>>a>>b;
        int aa = find(a),bb = find(b);
        if(aa!=bb){
            unit(a,b);
        }else{// 说明构成了环
            s = a,e = b;
            break;
        }
        addedge(a,b);
    }
    vis[s] = 1;
    dfs(s);
    int temp = e;
    res.push_back(temp);
    while(path[temp]){
        res.push_back(path[temp]);
        temp = path[temp];
    }
    sort(res.begin(),res.end());
    for(int i = 0; i < res.size(); i++){
        if(i>0){
            cout<<' ';
        }
        cout<<res[i];
    }
}

另外还可以采用深搜的方式，首先需要了解

在图的遍历中，往往设置了一个标记数组 vis 来记录顶点是否被访问过。但有些时候需要改变 vis 值的意义。令 vis 具有 3 种值并表示 3 种不同含义

vis = 0,表示该顶点没没有被访问
vis = 1,表示该顶点已经被访问，但其子孙后代还没被访问完，也就没从该点返回
vis = 2,，表示该顶点已经被访问，其子孙后代也已经访问完，也已经从该顶点返回
可以 vis 的 3 种值表示的是一种顺序关系和时间关系

《算法导论》334 页有这 4 种边的准确定义

边的定义

DFS 过程中，对于一条边 u->v
vis[v] = 0,说明 v 还没被访问，v 是首次被发现，u->v 是一条树边
vis[v] = 1,说明 v 已经被访问，但其子孙后代还没有被访问完（正在访问中），而 u 又指向 v，说明 u 就是 v 的子孙后代，u->v 是一条后向边，因此后向边又称返祖边，
vis[v] = 2,说明 v 已经被访问，其子孙后代也已经全部访问完，u->v 这条边可能是一条横叉边，或者前向边

注意：树边，后向边，前向边，都有祖先，后裔的关系，但横叉边没有，u->v 为横叉边，说明在这棵 DFS 树中，它们不是祖先后裔的关系它们可能是兄弟关系，堂兄弟关系，甚至更远的关系，如果是 dfs 森林的话，u 和 v 甚至可以在不同的树上

对于无向图而言，只存在树边和返祖边，当发现一条返祖边时，说明找到了环，这时输出所有 vis[i] = 1 的节点即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+7;
int vis[maxn];
int n;
vector<int> gra[10];
vector<int> res;
void addedge(int a,int b){
    gra[a].push_back(b);
    gra[b].push_back(a);
}
int flag = 0;
void findp(){  // 找环
    for(int i = 1; i <= n; i++){
        if(vis[i] == 1){
            res.push_back(i);
        }
    }
}
void dfs(int x,int p){
    for(int i = 0; i < gra[x].size(); i++){
        int to = gra[x][i];
        if(!vis[to]){
            vis[to] = 1;
            dfs(to,x);
        }else if(to!= p && vis[to]){
            if(!flag){
                flag = 1;
                findp();
            }
            return;
        }
    }
    vis[x] = 2;
}
int main(){
    cin>>n;
    memset(vis,0,sizeof(vis));
    for(int i = 0; i < n; i++){
        int a,b;
        cin>>a>>b;
        addedge(a,b);
    }
    vis[1] = 1;
    dfs(1,0);
    sort(res.begin(),res.end());
    for(int i = 0; i < res.size(); i++){
        if(i>0){
            cout<<' ';
        }
        cout<<res[i];
    }
}