发现否。牢固连接的组件 - 我的代码错误答案错误
我试图找不。图中紧密连接的组件。我写了下面的算法,但它失败了。计数变量存储了连接的组件编号。计数变量会增加:
- 当找到任何未访问的顶点(代码中的第1行)时,对于该顶点dfs,
- 当没有边缘从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:
- when any unvisited vertex is found (line 1 in code) and then for that vertex dfs is performed
- 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 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱,如果其他用户或者作者回复了您的评论,将不能在第一时间通知您!
发布评论