有向无环图DAG?
时间限制(普通/Java):1000MS/10000MS 运行内存限制:65536KByte
总提交:383 测试通过:92
描述
有向无环图（Directed Acyclic Graph，DAG）是图论中的一个重要模型。对于给定的一张有向图，你需要判断它是否存在环。
输入
输入包含多组数据。对于每组数据，第一行为一个正整数N（1<=N<=100），表示图中节点个数。接下来N行为描述该图的邻接矩阵。
输出
每组数据输出一行。如果该图中存在环，则输出yes，否则输出no
样例输入
2
0 1
0 0
2
0 1
1 0
样例输出
no
yes
题目来源
Narashy
分析：这个题估计是想多了，既然有环想到了拓扑排序，费了半天劲AC了，不过效率很低，后来想到了DFS，不过没有实现，今天没时间了，改天AC它。
#include <stdio.h>
#include <string.h>
int toposort(int n);
int f[101],o[101],v[101][101];
int main()
{
int n,i,j;
while (scanf("%d",&n)!=EOF)
{
memset(f,0,sizeof(f));
memset(o,0,sizeof(o));
for (i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
scanf("%d",&v[i][j]);
if (v[i][j])
{
f[j]++;
}
}
}
if (toposort(n))
{
printf("no\n");
}
else
printf("yes\n");
}
}
int toposort(int n)
{
int i,ff=1,j;
while (ff)
{
ff=0;
for (i=0;i<n;i++)
{
if (f[i]==0)
{
f[i]--;
ff=1;
for (j=0;j<n;j++)
{
if (v[i][j])
{
f[j]--;
}
}
}
}
}
ff=1;
for (i=0;i<n;i++)
{
if (f[i]>0)
{
ff=0;
break;
}
}
return ff;
}