Question

这道题我的Tarjan算法哪里错了，求大神指教：题目链接http://acm.hdu.edu.cn/showproblem.php?pid=4324

代码：
#include <iostream>
#include <string.h>
#include <stdio.h>
using namespace std;
const int N=2005;
int head[N],low[N],dfn[N],stack[N];
int index,m;
int temp[N];
char str[N][N];
typedef struct
{
int to;
int next;
}Node;
Node map[N*N];
void add(int u,int v)
{
map[index].to=v;
map[index].next=head[u];
head[u]=index++;
}
void Tarbfs(int k,int lay,int &scc_num)
{
temp[k]=1;
low[k]=lay;
dfn[k]=lay;
stack[++m]=k;
for(int i=head[k];i!=-1;i=map[i].next)
{
int t=map[i].to;
if(temp[t]==0)
Tarbfs(t,++lay,scc_num);
if(temp[t]==1)
low[k]=min(low[k],low[t]);
}
if(dfn[k]==low[k])
{
++scc_num;
do
{
low[stack[m]]=scc_num;
temp[stack[m]]=2;
}while(stack[m--]!=k);
}
return;
}
int Tarjan(int n)
{
int scc_num=0,lay=1;
m=0;
memset(temp,0,sizeof(temp));
memset(low,0,sizeof(low));
for(int i=1;i<=n;i++)
if(temp[i]==0) Tarbfs(i,lay,scc_num);
return scc_num;
}
int main()
{
int i,j,n,t=1,T;
scanf("%d",&T);
while(T--)
{
scanf("%d",&n);
memset(dfn,0,sizeof(dfn));
memset(head,-1,sizeof(head));
memset(stack,0,sizeof(stack));
index=0;
for(i=1;i<=n;i++)
scanf("%s",str[i]+1);
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(str[i][j]=='1')
{
add(i,j);
}
}
}
printf("Case #%d: ",t++);
int ret=Tarjan(n);
if(ret>=3) puts("Yes");
else puts("No");
}
return 0;
}

Answer 1

少了一个函数

int min(int i,int j)

{

if(i<=j) j=i;

return j;

}

还有把最后那里的Yes和No互换就行了，

我在Visual C++上检查还可以，

也通过了OJ，但不够优化

下图第二条记录就是测试数据