tarjan算法的第一个问题
喷我的脸。。。。手写叠式开成BOOL，我一直在找错了。。。
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define maxn 100005 const int MOD=1000000007; using namespace std; struct node
{
int to,next;
}edge[maxn*3]; int dfn[maxn],low[maxn],head[maxn],a[maxn],s[maxn];
bool instack[maxn];
int cnt,n,m,c,top;
long long ans1,ans2; void add(int x,int y)
{
edge[cnt].to = y;
edge[cnt].next = head[x];
head[x]=cnt++;
} void tarjan(int x)
{
dfn[x]=low[x]=++c;
instack[x] = true;
s[++top]=x; for(int i=head[x];i!=-1;i=edge[i].next)
{
int tmp = edge[i].to;
if(!dfn[tmp])
{
tarjan(tmp);
if(low[x]>low[tmp])
low[x] = low[tmp];
}
else if(instack[tmp])
{
if(low[x]>dfn[tmp])
low[x] = dfn[tmp];
}
}
if(low[x]==dfn[x])
{
int t;
int minx = MOD,sum = 0;
do{
t = s[top--];
instack[t] = false;
if(a[t]<minx)
{
minx = a[t];
sum = 1;
}
else if(a[t] == minx)
sum++;
}while(t!=x);
ans1+=minx;
ans2=(ans2*sum)%MOD;
}
} int main()
{
int p,b;
while(scanf("%d",&n)!=EOF)
{
cnt = 0;
memset(head,-1,sizeof(head));
memset(instack,0,sizeof(instack));
memset(dfn,0,sizeof(dfn));
memset(low,0,sizeof(low));
memset(s,0,sizeof(s)); for(int i=1;i<=n;i++)
scanf("%d",&a[i]);
scanf("%d",&m);
for(int i=1;i<=m;i++)
{
scanf("%d%d",&p,&b);
add(p,b);
}
c = 0,top = 0,ans1 = 0,ans2 = 1;
for(int k=1;k<=n;k++)
{
if(!dfn[k])
tarjan(k);
} printf("%I64d %I64d\n",ans1,ans2);
}
return 0;
}
tarjan算法的基础是DFS。
我们准备两个数组Low和Dfn。Low数组是一个标记数组，记录该点所在的强连通子图所在搜索子树的根节点的Dfn值（非常绕嘴，往下看你就会明确）。Dfn数组记录搜索到该点的时间，也就是第几个搜索这个点的。依据下面几条规则。经过搜索遍历该图（无需回溯）和对栈的操作，我们就能够得到该有向图的强连通分量。
- 数组的初始化：当首次搜索到点p时。Dfn与Low数组的值都为到该点的时间。
- 堆栈：每搜索到一个点，将它压入栈顶。
- 当点p有与点p’相连时，假设此时（时间为dfn[p]时）p’不在栈中。p的low值为两点的low值中较小的一个。
- 当点p有与点p’相连时，假设此时（时间为dfn[p]时）p’在栈中。p的low值为p的low值和p’的dfn值中较小的一个。
- 每当搜索到一个点经过以上操作后（也就是子树已经所有遍历）的low值等于dfn值，则将它以及在它之上的元素弹出栈。这些出栈的元素组成一个强连通分量。
- 继续搜索（也许会更换搜索的起点，由于整个有向图可能分为两个不连通的部分）。直到所有点被遍历。
因为每一个顶点仅仅訪问过一次。每条边也仅仅訪问过一次。我们就能够在O（n+m）的时间内求出有向图的强连通分量。可是，这么做的原因是什么呢？
Tarjan算法的操作原理例如以下：
- Tarjan算法基于定理：在不论什么深度优先搜索中，同一强连通分量内的全部顶点均在同一棵深度优先搜索树中。也就是说，强连通分量一定是有向图的某个深搜树子树。
- 能够证明。当一个点既是强连通子图Ⅰ中的点，又是强连通子图Ⅱ中的点，则它是强连通子图Ⅰ∪Ⅱ中的点。
- 这样，我们用low值记录该点所在强连通子图相应的搜索子树的根节点的Dfn值。
注意，该子树中的元素在栈中一定是相邻的，且根节点在栈中一定位于全部子树元素的最下方。
- 强连通分量是由若干个环组成的。
所以，当有环形成时（也就是搜索的下一个点已在栈中）。我们将这一条路径的low值统一，即这条路径上的点属于同一个强连通分量。
- 假设遍历完整个搜索树后某个点的dfn值等于low值，则它是该搜索子树的根。
然后，它的上方（它包含自己的）所有的元素都堆叠组成的强连接组件。