图结构练习——判断给定图是否存在合法拓扑序列
Time Limit: 1000ms Memory limit: 65536K 有疑问？点这里^_^
题目描述
给定一个有向图，判断该有向图是否存在一个合法的拓扑序列。
输入
输入包含多组，每组格式如下。
第一行包含两个整数n，m，分别代表该有向图的顶点数和边数。(n<=10)
后面m行每行两个整数a b，表示从a到b有一条有向边。
输出
若给定有向图存在合法拓扑序列，则输出YES；否则输出NO。
示例输入
1 0
2 2
1 2
2 1
示例输出
YES
NO 网上看到有人的思路很巧妙，忍不住就稍作修改，贴了上来：http://www.cnblogs.com/luyingfeng/archive/2013/07/29/3223090.html第一种思路是直接判断环是否存在的思路，这种思路采用dfs算法，是非常规思路：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
int vis[];
int m,n,u,v;
int map[][];
int dfs(int u)//深度优先搜索遍历
{
vis[u]=-;//标记-1，正在访问
for(v=; v<=m; v++)
{
if(map[u][v])//如果v是u的后继元素
{
if(vis[v]<)//如果v元素是正在访问中的状态
return ;//存在自环
//如果存在的不是自环
if(!vis[v]&&!dfs(v))//v元素还没有被访问而且v的后继元素和前面的正在访问的元素构成了回路
return ;
}
}
//若果u的后继结点全部没有形成自回路或者是回路
vis[u]=;//标记1，访问完了，删除此节点
return ;
}
int toposort()
{
for(u=; u<=m; u++)
{
if(!vis[u])//如果u节点还没有访问
{
if(!dfs(u))//如果dfs的返回值是0，强制退出排序函数toposort，表明存在环
return ;
}
}
return ;//如果u从1到m全部遍历完
}
int main()
{
while(~scanf("%d %d",&m,&n)&&(m+n!=))
{
memset(vis,,sizeof(vis));
memset(map,,sizeof(map));
for(int i=; i<=n-; i++)
{
scanf("%d %d",&u,&v);
map[u][v]=;
}
if(toposort())//如果返回值是1，不存在回路，无论是自回路或者是回路
printf("YES\n");
else printf("NO\n");//如果返回值是0
}
return ;
}
常规思路，也是书上的思路，即判断是否存在入度为0的节点，若在循环未结束的时候，就找不到入度为0的节点，则必存在环
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int map[][],count[];
int flag;
int u,v,vis;
int main()
{
int m,n;
while(~scanf("%d %d",&m,&n)&&(n!=||m!=))
{
memset(map,,sizeof(map));
memset(count,,sizeof(count));//每个节点的入度初始为0；
vis=;//标记变量，用于帮助最后输出
for(int i=; i<=n-; i++)
{
scanf("%d %d",&u,&v);
map[u][v]=;
count[v]++;
}
for(int i=; i<=m-; i++)
{
int flag=;
for(u=; u<=m; u++)
{
if(count[u]==)
{
flag=;//只要有入度为0的点就变为1
count[u]--;//删除掉这个节点
for(v=; v<=m; v++)//凡是与该节点有关的所有结点入度去掉1；
{
if(map[u][v])
{
count[v]--;
}
}
break;
}
}
if(flag==)//如果没有入度为0的点，就代表没有拓扑序列
{
vis=;
break;
}
}
if(vis==)
printf("YES\n");
else printf("NO\n");
}
return ;
}
以上两种算法全部采用邻接矩阵的方法，但是采用邻接表的方法更具有一般性，这也是以上两种方法的不足之处。
以下是用邻接表的方法：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct vode
{
int v;
struct vode *next;
};
struct vode *f[];
int count[];
int stack[],top=;
int m,n;
int topsort()
{
int i,sum=;
int flag;
while()
{
flag=;
for(i=;i<=m;i++)
{
if(count[i]==)
{
stack[top++]=i;
sum++;
count[i]--;//删除i节点
struct vode *p;
for(p=f[i];p!=NULL;p=p->next)//把i节点的邻接点的入度都减1
{
int t=p->v;
count[t]--;
}
flag=;
}
if(flag==)break;//如果找到了入度是0的节点，从头开始再找入度是0的节点
}
if(flag==)//循环完了之后再也找不到入度是0的节点，这时候可能会有环，也可能没有环
{
break;
}
}
return sum;
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
int i;
memset(count,,sizeof(count));
for(i=;i<=m;i++)
f[i]=NULL;
for(i=;i<=n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
count[v]++;
struct vode *p;
p=(struct vode *)malloc(sizeof(struct vode));
p->v=v;
p->next=f[u];
f[u]=p;
} int sum=topsort();
if(sum!=m)printf("NO\n");
else printf("YES\n");
/*
通过这个循环可以得到最终每个节点的入度，如果是合法的拓扑序列，最终的结果应当都是-1
for(i=1;i<=m;i++)
printf("%d ",count[i]);
printf("\n");
通过下面这个循环可以得到最终一个拓扑序列（如果合法），这个序列可能只是合法序列当中的一个
for(i=1;i<=m;i++)
printf("%d ",stack[i]);
printf("\n");
*/
}
return ;
}
简化后的代码：
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct vode
{
int v;
struct vode *next;
};
struct vode *f[];
int m,n;
int rudu[];
int stack[],top;
void hs()
{
int i,k=;
while(k=!k)
for(i=;i<=m;i++)
if(rudu[i]==)
{
k=;
rudu[i]--;
stack[top++]=i;
struct vode *p;
for(p=f[i];p!=NULL;p=p->next)
rudu[p->v]--;
break;
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF)
{
memset(f,,sizeof(f));
memset(rudu,,sizeof(rudu));
memset(stack,,sizeof(stack));
top=;
int i;
for(i=;i<=n;i++)
{
int u,v;
scanf("%d%d",&u,&v);
rudu[v]++;
struct vode *p;
p=(struct vode *)malloc(sizeof(struct vode));
p->v=v;
p->next=f[u];
f[u]=p;
}
hs();
/*//下面的循环可以显示出拓扑序列
for(i=0;i<=top-1;i++)
printf("%d ",stack[i]);
printf("\n");
*/
if(top==m)printf("YES\n");
else printf("NO\n");
}
return ;
}
测试数据：
5 4
1 3
2 3
3 4
3 5
输出：
YES
-1 -1 -1 -1 -1
1 2 3 4 5
测试连接：http://wenku.baidu.com/view/bb32ee2e4b73f242336c5f53.html