判环的几种方法
拓扑排序判环
- 对于有向图：
//有向图环判断
#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
*/
- 对于无向图
因为是双向边，那么我们需要先把度数为\(1\)的点加入(区别与上面有向图(度数为0的加入))队列，
for(int i = 1; i <= n; i++)
if(d[i] == 1)
q.push(i),vis2[i] = true;
然后当]之前没有访问过且减去和上一个点所连的边带来的影响之后度数是不是小于等于1，是的话加入队列里面。
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\)的点在环上
例题：H. Mad City
// 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判环
\(color\)代表每个结点的状态，\(-1\)代表还没被访问，\(0\)代表正在被访问，\(1\)代表访问结束
如果一个状态为\(0\)的结点，与他相连的结点状态也为\(0\)的话就代表有环,这个可以用\(dfs\)实现
// AC one more times
// nndbk
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
vector <int> vec[N];
int color[N];
bool dfs(int u) {
color[u] = 0; // 0表示正在访问
for (int v: vec[u]) {
if (color[v] == 0) { //如果正在访问的点又被访问到则代表有环
return false;
} else if (color[v] == -1) { // -1代表还没有访问
if (!dfs(v)) {
return false;
}
}
}
color[u] = 1; // 1代表访问结束
return true;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 0; i < m; i++) {
int from, to;
cin >> from >> to;
vec[from].push_back(to);
}
memset(color, -1, sizeof(color));
auto check = [&] () -> bool {
for (int i = 1; i <= n; i++) {
if (color[i] == -1) {
if (!dfs(i)) {
return false;
}
}
}
return true;
};
puts(check() ? "no have" : "have");
return 0;
}
dfs找环数和找路径
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6;
int cnt; //计数
int nums = 0;
int vis[N],pre[N];
vector<int>e[N];
void dfs(int u,int fa){ //dfs
vis[u] = 1;
int sz = e[u].size();
for(int i = 0;i < sz;i++){
int v = e[u][i];
if(v==fa) continue; //如果是无向的 a-->b 的同时也有 b-->a,所以直接排除另外的一种情况
if(vis[v]==0){ //如果没有访问就标记当前元素的前一个元素
pre[v] = u;
dfs(v,u); //并且一直递归访问下去
}else if(vis[v]==1){
int temp = u;
int count = 1;
while (temp!=v) //找路径
{
cout << temp << " ";
count++;
temp = pre[temp];
}
cout << v << endl;
//cout << endl;
nums++; //环数+1
}
}
vis[u] = 2;
}
int main()
{
int n,m;int u,v; //n为点数 m为边数 u是起点v是终点
cin >> n >> m;
for(int i = 1;i <= m;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
*/