判断无向图是否有环dfs

前面有用并查集判断无向图是否有环，这次用dfs来判断是否有环。
图只有树边和反向边，如果有反向边那么就有环，否则就是树或森林。

#include <iostream>

using namespace std;

const int M=501;

bool g[M][M];

bool visit[M];

bool flag;

int v,e;

bool dfs(int i,int pre)

{

visit[i]=true;

for(int j=1;j<=v;j++)

if(g[i][j])

{

if(!visit[j])

return dfs(j,i);

else if(j!=pre) //如果访问过，且不是其父节点，那么就构成环

return false;

}

int main()

{

int i,j;

while(cin>>v>>e)

{

memset(g,0,sizeof(g));

while(e--)

{

cin>>i>>j;

g[i][j]=g[j][i]=true;

}

memset(visit,0,sizeof(visit));

flag=dfs(1,0);

if(flag)

cout<<"no\n";

else

cout<<"yes\n";

}

return 0;

}

posted on 2011-09-13 11:50 大大木马阅读(7498) 评论(1) 编辑收藏引用

文章档案(2)

搜索

积分与排名

积分 - 62343

排名 - 353

最新评论

1. re: 会场安排问题（贪心算法）
@lizi
这个没有问题啊，只需要一个会场就安排了所有的活动
--patrick
2. re: 工作分配问题（回溯算法）
评论内容较长,点击标题查看
--45
3. re: 会场安排问题（贪心算法）
貌似有问题吧，测试数据
5
1 2
3 4
5 6
7 8
9 10
输出1
--lizi
4. re: 会场安排问题（贪心算法）
评论内容较长,点击标题查看
--张三
5. re: HDU 1698
写的很清晰，借鉴
--Qiu

阅读排行榜

评论排行榜

常用链接

留言簿(1)

随笔档案(53)

文章档案(2)

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理