还是POJ_2762,前段时间用Kosaraju算法解决掉了,不过解决强连通分量的线性时间复杂度的算法还有两个,Tarjan,Gabow,今天把Tarjan看了下,感觉基本思想还是不难的,实现起来也算容易,不过我还不能证明其正确性。
Tarjan算法的基本思路就是,利用DFS去求强连通分量,具体步骤如下:
1.任意选取一个顶点做为DFS的起始位置,进行DFS。
2.在每次DFS中,先把discoverTime[now_node],和lowlink[now_node]赋值为当前搜索时间,并把当前结点压入栈内,然后查看当前结点的所有后继结点,如果其后继结点尚未访问,则继续DFS下去,并且lowlink[now_node] = min(lowlink[now_node],lowlink[当前结点的后继]).否则就检查该后继结点是否还在栈中,如果是的话则有 lowlink[now_node] = min(lowlink[now_node],discoverTime[该后继结点]);
说明:lowlink[u]表示包括u结点及其所有后继结点中最早被发现的时间,discoverTime[u]表示u结点的被发现时间.
3.查看lowlink[now_node]是否等于discoverTime[now_node],如果是,则说明该结点是一个强连通分量的根,则把栈中的元素弹出,直到弹出的元素是now_node为止。至此就求出了一个SCC。
4.如果图中尚有未被访问的结点,那么就以这些结点中的任意一个作为起始位置,再次进行DFS,回到步骤二,直到所有结点都被访问过。至此,图的所有SCC都被求出.
伪代码如下:
algorithm tarjan is
input: graph G = (V, E)
output: set of strongly connected components (sets of vertices)
index := 0
S := empty
for each v in V do
if (v.index is undefined) then
strongconnect(v)
end if
repeat
function strongconnect(v)
// Set the depth index for v to the smallest unused index
v.index := index
v.lowlink := index
index := index + 1
S.push(v)
// Consider successors of v
for each (v, w) in E do
if (w.index is undefined) then
// Successor w has not yet been visited; recurse on it
strongconnect(w)
v.lowlink := min(v.lowlink, w.lowlink)
else if (w is in S) then
// Successor w is in stack S and hence in the current SCC
v.lowlink := min(v.lowlink, w.index)
end if
repeat
// If v is a root node, pop the stack and generate an SCC
if (v.lowlink = v.index) then
start a new strongly connected component
repeat
w := S.pop()
add w to current strongly connected component
until (w = v)
output the current strongly connected component
end if
end function
POJ_2762_Tarjan实现代码如下:
#include<iostream>
#include<vector>
#include<stack>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAXN = 1001;
vector<int> g[MAXN];//adjlist
stack<int> S;
int vis[MAXN],store[MAXN],scc[MAXN][MAXN],scccnt,DFN[MAXN],LOW[MAXN],belong[MAXN],deg[MAXN];
#define MIN(a,b) a>b?b:a
void addEdge(int u,int v)
{
g[u].push_back(v);
}
void init()
{
for(int i=0;i<MAXN;i++)g[i].clear();
while(!S.empty())S.pop();
memset(vis,0,sizeof(vis));
memset(store,0,sizeof(store));
memset(scc,0,sizeof(scc));
scccnt = 0;
}
void tarjan(int u,int n,int &time)
{
DFN[u] = LOW[u] = time++;
S.push(u);
vis[u] = 1;store[u] = 1;
for(int i=0;i<g[u].size();i++)
{
if(!vis[g[u][i]])//not visited
{
tarjan(g[u][i],n,time);
LOW[u] = MIN(LOW[u],LOW[g[u][i]]);
}
else if(store[g[u][i]])//in the stack
{
LOW[u] = MIN(LOW[u],DFN[g[u][i]]);
}
}
if(LOW[u]==DFN[u])
{
int v;
do
{
v = S.top();
S.pop();
store[v] = 0;//out from the stack
belong[v] = scccnt;
}while(v!=u);
scccnt++;
}
}
void make_SCCG(int n)
{
for(int i=1;i<=n;i++)
{
for(int j=0;j<g[i].size();j++)
{
if(belong[i]!=belong[g[i][j]])
{
scc[belong[i]][belong[g[i][j]]]=1;
}
}
}
}
bool calldfs2(int n)
{
memset(vis,0,sizeof(vis));
make_SCCG(n);
memset(vis,0,sizeof(vis));
memset(deg,0,sizeof(deg));
for(int i=0;i<scccnt;i++)
{
for(int j=0;j<scccnt;j++)
{
if(scc[j][i])deg[i]++;
}
}
int u,cnt;
for(int i=0;i<scccnt;i++)
{
cnt = 0;
for(int j=0;j<scccnt;j++)
{
if(deg[j]==0&&!vis[j])
{
u = j;
cnt++;
}
}
if(cnt!=1)return false;
vis[u] = 1;
for(int j=0;j<scccnt;j++)
{
if(scc[u][j])deg[j]--;
}
}
return true;
}
int main()
{
int n,m,t;
scanf("%d",&t);
while(t--)
{
scanf("%d%d",&n,&m);
init();
for(int i=0;i<m;i++)
{
int a,b;
scanf("%d%d",&a,&b);
addEdge(a,b);
}
int time = 1;
for(int i=1;i<=n;i++)
{
if(!vis[i])tarjan(i,n,time);
}
bool ok = calldfs2(n);
if(ok) printf("Yes\n");
else printf("No\n");
}
return 0;
}
参考资料:
[url]http://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm#Overview [/url]
- 大小: 15.4 KB
分享到:
相关推荐
《Tarjan算法——高效求解有向图强连通分量》 Tarjan算法是一种用于求解有向图强连通分量的高效算法,它基于深度优先搜索(DFS)策略,由著名计算机科学家Robert Tarjan提出。在有向图中,如果两个顶点之间存在双向...
本资源“图论- 图的连通性- Tarjan 求双连通分量.rar”着重讨论了图的连通性以及一种用于求解双连通分量的著名算法——Tarjan算法。 首先,我们理解一下图的连通性。一个无向图是连通的,如果任意两个顶点之间都...
本阶段我们将聚焦于图论中的一个核心概念——强连通分量,通过深入理解并练习相关算法来提升解题能力。 强连通分量是图论中的一个基本概念,它在有向图中尤为关键。有向图是由顶点和有方向的边构成的图,每个边都有...
"tarjane"这个项目似乎专注于实现一种特定的数据分析算法——Tarjan的强连通分量算法。这个算法是图论中的一个重要概念,用于识别图中强连通组件。下面将详细介绍这个算法及其在MATLAB中的应用。 **Tarjan的强连通...
6. 强连通分量:在有向图中,强连通分量是指图中任何两个顶点都可以相互到达的子图。Tarjan算法可以有效地找出这些分量。 7. 最小生成树:Prim算法和Kruskal算法用于在加权无向图中找出连接所有顶点的最小权值边集...
- **强连通分量的求法**: 常用的算法有Kosaraju算法和Tarjan算法。 - **缩点**: 在处理强连通分量时,可以将每个强连通分量视为一个节点来进行简化。 #### Tarjan算法中的`dfn`和`low`变量 在Tarjan算法中,为了...
Tarjan算法可以有效地找出强连通分量。 4. 最小生成树: - Kruskal算法:根据边的权重从小到大选择,避免形成环。 - Prim算法:从一个节点开始,每次添加一条最小的边,使生成树包含更多的节点。 5. 欧拉路径和...
- **图算法**:解决这类问题通常需要用到图论中的经典算法,比如拓扑排序、DFS、BFS 或 Tarjan算法来寻找强连通分量。 ### 3. 解题思路 #### 无入度检测SCC - **算法选择**:使用Tarjan算法或者Kosaraju算法可以...
6. **强连通分量**:TARJAN算法用于识别有向图中的强连通分量,即在有向图中任意两点之间都存在双向路径的子图。 7. **弦图**:弦图是一种特殊的图结构,文档中介绍了如何判断一个图是否为弦图,以及弦图的PERFECT ...
给定一个有向图,你需要找出其中的强连通分量,即图中任意两个节点都可以互相到达的子图。一开始尝试使用 Tarjan 算法求解,但由于某些原因导致栈溢出。因此,改用了深度优先搜索(DFS)的简单实现,通过遍历每个未...
- **TARJAN强连通分量**:一种高效的强连通分量算法,基于深度优先搜索。通过维护每个顶点的低链值,可以在线性时间内找到所有强连通分量。 - **弦图判断与完美消除点排列**:弦图是一种特殊的图,其中每个长度至少...
Tarjan算法和Kosaraju算法常用于检测和找出强连通分量。 7. 最小生成树: - Kruskal算法:按边的权重从小到大选择边,同时避免形成环,直到连接所有顶点。 - Prim算法:从任意一个顶点开始,每次添加一条最小的边...
- **TARJAN强连通分量**:讲述了Tarjan算法用于求解强连通分量的方法。 - **弦图判断**:介绍了如何判断一个图是否为弦图。 - **弦图的PERFECT ELIMINATION点排列**:解释了如何对弦图进行完美消除排序。 - **稳定...
在分析和操作图时,我们经常会遇到一些经典算法,比如寻找最小生成树(Prim或Kruskal算法)、判断图是否连通(DFS或BFS)、查找强连通分量(Tarjan算法)等。这些算法的实现和优化也是“mygraphtest”项目中可能涉及...
- Tarjan算法用于计算无向图的点双连通分量,它并没有直接使用贪心策略。 - **Bellman-Ford算法**: - Bellman-Ford算法是一种用于计算带权图中单源最短路径的算法,可以处理含有负权重边的情况。 - 其最坏情况...