使用dfs的无向图中的圈

Question

请告诉我为什么这段代码不能分析无向图中是否有循环？代码如下。这是Spoj上的PT07Y问题。我正在做的是取一个节点并执行dfs。当执行dfs时，如果我访问同一个节点，那么我说有一个循环。从一个节点执行dfs后，我使访问的数组为假，并为下一个节点执行，直到我得到一个周期或所有节点都被访问。

#include <iostream>
#include <bits/stdc++.h>
using namespace std;
bool vis[10001];

int dfs(int n,vector <int> v[],int a)
{
    vis[n]=true;
    for(int i=0;i<v[n].size();i++)
    {
        if(v[n][i]==a)
            return 1;
        if(vis[v[n][i]]==false)
        {
            dfs(v[n][i],v,a);
        }
    }
    return 0;
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,m,i,a,b,cc;
    cin>>n>>m;
    vector <int> v[n+1];
    memset(vis,false,n+1);
    for(i=0;i<m;i++)
    {
        cin>>a>>b;
        v[a].push_back(b);
    }
    for(i=1;i<=n;i++)
    {
        if(dfs(i,v,i))
        {
            cout<<"NO"<<endl;
            return 0;
        }
        memset(vis,false,sizeof(vis));
    }
    cc=-1;
    for(i=1;i<=n;i++)
    {
        if(vis[i]==false)
        {
            cc++;
            if(cc>0)
            {
                cout<<"NO"<<endl;
                return 0;
            }  
            int m= dfs(i,v,-1);
        }
    }
    cout<<"YES"<<endl;
    return 0;
}

Answer 1

图形被指定为无向，但输入格式将只指定每条边一次（对于其中一个方向）。因此，当您从输入中读取类似于12的行时，您必须通过2扩展1的邻接列表，并通过1扩展2的邻接列表。但是，在您的程序中，您只存储第一个方向。因此，图形的表示将不完整。

要解决此问题，请扩展输入处理以存储两个方向：

  for (i = 0; i < m; i++) {
    cin >> a >> b;
    v[a].push_back(b);
    v[b].push_back(a);
  }

您的dfs方法行为不正确：

dfs方法如果找到目标顶点，则返回1。但是，这个返回代码不会沿着递归传播。因此，当您在dfs方法中进行递归调用dfs（v[n][i]， v， a）；，并且该调用返回1时，当前的dfs调用将忽略此结果。如果当前dfs调用没有在当前邻接列表中找到目标顶点，那么它将完成循环的并返回0。

要解决此问题，您必须确保如果递归dfs调用返回1，则for循环被中止，当前dfs调用也会返回1，例如：

if (dfs(v[n][i], v, a, n) == 1) {
  return 1;
}

应用此修复程序后，会发现另一个问题：当dfs方法在相邻顶点列表中发现目标顶点时，它不排除当前顶点所在的边缘。所以如果你有一个图1

要解决此问题，可以跟踪每个dfs调用的父顶点。最初，没有设置父项（即-1）。当您从a转到b时，您将以父级身份传递a。在b，您将忽略b的邻接列表中的父a：

所以你的dfs看起来像这样：

int dfs(int n, vector<int> v[], int a, int parent) {
  vis[n] = true;
  for (int i = 0; i < v[n].size(); i++) {
    if (v[n][i] == parent) {
      continue;
    }
    if (v[n][i] == a)
      return 1;
    if (vis[v[n][i]] == false) {
      if (dfs(v[n][i], v, a, n) == 1) {
        return 1;
      }
    }
  }
  return 0;
}

实现的性能不是最佳的（这会导致SPOJ超时）。您可以通过在main函数中的每次循环检查后不清除vis数组来改善这一点。相反，重新使用vis数组，仅对尚未访问的顶点执行循环检查：

  for (i = 1; i <= n; i++) {
    if (vis[i] == false) {
      if (dfs(i, v, i, -1)) {
        cout << "NO" << endl;
        return 0;
      }
    }
  }
  memset(vis, false, sizeof(vis));

这足以让您的代码被SPOJ接受。

然而，您可以进一步优化代码中的连接性检查：您可以重用，而不是在循环检查后清除vis数组，并为每个顶点执行另一系列dfs，直到发现第二个组件VIS数组，并在循环检查后简单地检查是否有任何未访问的顶点。这将允许您完全省略第二个dfs系列。