判环的几种方法

Nannan Lv5
  2024-02-12 17:35 2024-02-12 17:35 Created   2024-09-30 19:43:45 2024-09-30 19:43:45 Updated      

判环的几种方法

拓扑排序判环

  • 对于有向图：
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
//有向图环判断
#include<bits/stdc++.h>
using namespace std;

vector<int>edge[10001];
int n,m,d[10001];
queue<int>q;
inline void TopoSort()
{
	int cnt = 0;
	for(int i = 1;i<=n;i++)
	{
		if(!d[i])
		{
			q.push(i);
			++cnt;
		}
	}

	while(!q.empty())
	{
		int x = q.front();
		q.pop();
		for(auto y:edge[x])
			if(--d[y]==0)
			{
				q.push(y);
				++cnt;
			}
	}
	if(cnt==n)cout<<"No\n";
	else cout<<"Yes\n";
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	for(int i =1 ;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		edge[x].push_back(y);
		++d[y];
	}
	TopoSort();
	return 0;
}
/*
4 4
1 2
2 3
3 4
1 4

No
*/
  • 对于无向图

因为是双向边，那么我们需要先把度数为的点加入(区别与上面有向图(度数为0的加入))队列，

1
2
3
for(int i = 1; i <= n; i++)
       if(d[i] == 1)
           q.push(i),vis2[i] = true;

然后当]之前没有访问过且减去和上一个点所连的边带来的影响之后度数是不是小于等于1，是的话加入队列里面。

1
2
3
4
5
6
7
while(!q.empty())
  {
      int u = q.front();  q.pop();
      for(auto v : e[u])
          if(--d[v] <= 1 && !vis2[v])
              q.push(v),vis2[v] = true;
  }

最后度数大于的点在环上

板子：

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,d[N];
vector<int> e[N];
bool vis[N];

void toposort()
{
    queue<int> q;
    for(int i = 1;i <= n; i++)
        vis[i] = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] == 1)
            q.push(i),vis[i] = true;
    while(!q.empty())
    {
        int u = q.front();  q.pop();
        
        for(auto v : e[u])
            if(--d[v] <= 1 && !vis[v])
                q.push(v),vis[v] = true;
    }   
}



int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);

    cin>>n;
    for(int i = 1; i <= n; i++)
    {
        int u , v;    cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
        d[u]++;
        d[v]++;
    }
    toposort();
    set<int>s;
    for(int i = 1;i <= n; i++)
        if(d[i]>1)s.insert(i);
    for(auto x : s)
        cout<<x<<" ";
    cout<<"\n";
    return 0;
}

例题：H. Mad City 

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
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
const int N = 2e5 + 10;
int n,a,b,d[N];
bool vis[N];
ll dist1[N],dist2[N];
vector<int> e[N];
bool vis2[N];
int tot,l[N];
void toposort()
{
    queue<int> q;
    tot = 0;
    for(int i = 1;i <= n; i++)
        vis2[i] = 0;
    for(int i = 1; i <= n; i++)
        if(d[i] == 1)
            q.push(i),vis2[i] = true;
    while(!q.empty())
    {
        int u = q.front();  q.pop();
        //l[++tot] = u;
       // cout<<"u = "<<u<<"\n";
        for(auto v : e[u])
            if(--d[v] <= 1 && !vis2[v])
                q.push(v),vis2[v] = true;
    }   

    // for(int i = 1;i <= tot; i++)
    //     cout<<l[i]<<" ";
    // cout<<"\n";
}



int main()
{
    ios::sync_with_stdio(false);   cin.tie(nullptr), cout.tie(nullptr);
    int t;
    cin>>t;
    while(t--)
    {
        cin>>n>>a>>b;

        for(int i = 1;i <= n; i++)
            e[i].clear(),dist1[i] = 0,dist2[i] = 0,d[i] = 0;
        for(int i = 1; i <= n; i++)
        {
            int x , y;    cin>>x>>y;
            e[x].push_back(y);
            e[y].push_back(x);
            d[y]++;
            d[x]++;
        }
        toposort();
        queue<pair<int,ll>>q;
        q.push({a,0});
        dist1[a] = 0;
        memset(vis,false,sizeof(vis));
        vis[a] = true;

        while(!q.empty())
        {
            auto i = q.front();
            q.pop();
            int u = i.first,dis = i.second;
            for(auto v : e[u])
            {
                if(!vis[v])
                {
                    vis[v] = true;
                    dist1[v] = dis + 1;
                    q.push({v,dist1[v]});
                }
            }
        }
        
        q.push({b,0});
        dist2[b] = 0;
        memset(vis,false,sizeof(vis));
        vis[b] = true;

        while(!q.empty())
        {
            auto i = q.front();
            q.pop();
            int u = i.first,dis = i.second;
            for(auto v : e[u])
            {
                if(!vis[v])
                {
                    vis[v] = true;
                    dist2[v] = dis + 1;
                    q.push({v,dist2[v]});
                }
            }
        }
        bool ok = false;
        // for(int i = 1;i <= n;i++)
        //     cout<<d[i]<<" ";
        // cout<<"\n";
        //  for(int i = 1;i <= n;i++)
        //     cout<<dist1[i]<<" ";
        // cout<<"\n";
        //  for(int i = 1;i <= n;i++)
        //     cout<<dist2[i]<<" ";
        // cout<<"\n";
        for(int i = 1;i <= n;i++)
        {
            if(d[i]>1&&dist1[i]>dist2[i])ok = true;
        }
        if(ok)cout<<"YES\n";
        else cout<<"NO\n";
    }
    return 0;
}

dfs判环

代表每个结点的状态，代表还没被访问，代表正在被访问，代表访问结束
如果一个状态为的结点，与他相连的结点状态也为的话就代表有环,这个可以用实现

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
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
 
const int N = 1e5 + 10;
vector <int> e[N];
int vis[N];
int n, m;
bool dfs(int u) {
    vis[u] = 1; // 1表示正在访问
    for (int v: e[u]) {
        if (vis[v] == 1) { //如果正在访问的点又被访问到则代表有环
            return false;
        } else if (vis[v] == 0) { // 0代表还没有访问
            if (!dfs(v)) {
                return false;
            }
        }
    }
    vis[u] = 2; // 2代表访问结束
    return true;
}

bool check(){
    for (int i = 1; i <= n; i++) {
            if (vis[i] == 0) {
                if (!dfs(i)) {
                    return false;
                }
            }
        }
        return true;
    };

int main()
{

    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u,v;  cin >> u >> v;
        e[u].push_back(u);
    }
    memset(vis, 0, sizeof(vis));
    
    puts(check() ? "no have" : "have");
    return 0;
}

dfs找环数和找路径

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
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;


int nums = 0;
int vis[N],pre[N];

vector<int>e[N];
void dfs(int u,int fa){     //dfs
    vis[u] = 1;
    for(auto v : e[u]){  
        if(v==fa)   continue;   //如果是无向的 a-->b 的同时也有 b-->a,所以直接排除另外的一种情况
        if(vis[v]==0){          //如果没有访问就标记当前元素的前一个元素
            pre[v] = u;
            dfs(v,u);           //并且一直递归访问下去
        }else if(vis[v]==1){
            int tmp = u,cnt = 1;//环的长度
            while(tmp != v)
            {
                cout<<tmp<<" ";
                cnt++;
                tmp = pre[tmp];
            }
            cout<<v<<"\n";
            nums++;
        }
    }
    vis[u] = 2;
}
int main()
{
    int n;int u,v;        //n为点数  m为边数    u是起点v是终点
    cin >> n;
    for(int i = 1;i <= n;i++){
        cin >> u >> v;
        e[u].push_back(v);
        e[v].push_back(u);
    }

    for(int i = 1;i <= n;i++){      //可能是非联通图
        if(vis[i]==0)               //每一次可以访问完和该点相连的所有点
            dfs(i,-1);
    }
    cout << nums << endl;           //环数
    return 0;
}

/*
3 3
2 1
3 2
1 3
*/
  • Title: 判环的几种方法
  • Author: Nannan
  • Created at : 2024-02-12 17:35:00
  • Updated at : 2024-09-30 19:43:45
  • Link: https://redefine.ohevan.com/2024/02/12/判环的几种方法/
  • License: This work is licensed under CC BY-NC-SA 4.0.
Comments
On this page
判环的几种方法
  1. 判环的几种方法
    1. 拓扑排序判环
    2. dfs判环
      1. dfs找环数和找路径