发现否。牢固连接的组件 - 我的代码错误答案错误

发布于 2025-01-22 04:03:40 字数 1608 浏览 1 评论 0原文

我试图找不。图中紧密连接的组件。我写了下面的算法,但它失败了。计数变量存储了连接的组件编号。计数变量会增加:

  1. 当找到任何未访问的顶点(代码中的第1行)时,对于该顶点dfs,
  2. 当没有边缘从subtree出去时,最低到达时间低于顶点本身的到达时间时(代码中的第2行)

我试图评论我的代码。请告诉我在哪里错了。

    int noOfStronglyConnectedComp(int V, vector<int> adj[])
    {
        vector<bool> visited(V,false);
        vector<int> arr(V);    //arrival time of a vertex: when a vertex is first reached
        int timer=0;           //allocated to arrival time
        int count=0;           //stores no. of connected components
        for(int i=0;i<V;i++)
        {
            if(!visited[i])
               { 
                   count++;  //line 1
                   dfs(i,adj,visited,arr,timer,count,i);
               }
        }
        return count;
        
    }
    int dfs(int source,vector<int> adj[], vector<bool> &visited,vector<int> &arr, int &timer, int &count,int parent)
    {
        visited[source]=1;        //node marked visited
        arr[source]=timer++;      //arrival time is set
        int lowest=arr[source];   //lowest stores the edge going out of the subtree with the lowest arrival time
        for(int i=0;i<adj[source].size();i++)
            {
                if(!visited[adj[source][i]])
                    lowest=min(lowest,dfs(adj[source][i],adj,visited,arr,timer,count,parent));
                else
                    lowest=min(lowest,arr[adj[source][i]]);
            }
        if(lowest==arr[source] && source!=parent) 
        count++;    //line 2
        return lowest;    
    }

I was trying to find no. of strongly connected components in a graph. I wrote the below algo but it is failing. The count variable stores the no.of connected components. Count variable is incremented:

  1. when any unvisited vertex is found (line 1 in code) and then for that vertex dfs is performed
  2. when no edge going out of the subtree with the lowest arrival time lower than the arrival time of the vertex itself is found (line 2 in code)

I have tried to comment my code. Please tell where I am wrong.

    int noOfStronglyConnectedComp(int V, vector<int> adj[])
    {
        vector<bool> visited(V,false);
        vector<int> arr(V);    //arrival time of a vertex: when a vertex is first reached
        int timer=0;           //allocated to arrival time
        int count=0;           //stores no. of connected components
        for(int i=0;i<V;i++)
        {
            if(!visited[i])
               { 
                   count++;  //line 1
                   dfs(i,adj,visited,arr,timer,count,i);
               }
        }
        return count;
        
    }
    int dfs(int source,vector<int> adj[], vector<bool> &visited,vector<int> &arr, int &timer, int &count,int parent)
    {
        visited[source]=1;        //node marked visited
        arr[source]=timer++;      //arrival time is set
        int lowest=arr[source];   //lowest stores the edge going out of the subtree with the lowest arrival time
        for(int i=0;i<adj[source].size();i++)
            {
                if(!visited[adj[source][i]])
                    lowest=min(lowest,dfs(adj[source][i],adj,visited,arr,timer,count,parent));
                else
                    lowest=min(lowest,arr[adj[source][i]]);
            }
        if(lowest==arr[source] && source!=parent) 
        count++;    //line 2
        return lowest;    
    }

如果你对这篇内容有疑问,欢迎到本站社区发帖提问 参与讨论,获取更多帮助,或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。
列表为空,暂无数据
我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站,即表示您同意使用 Cookies 和您的相关数据。
原文