重剑无锋
我生待明日,万事成蹉跎
posts - 13,  comments - 6,  trackbacks - 0
bnu5472(hdu1272)无向
bnu5525(hdu1325)有向

这两道题有个需要注意的地方,就是它的边是随机出现的,并不是和其他的并查集的题一样,从1-n什么的,所以用一个数组,或者map存放着存在的边,判断一个图是不是为树,如果是无向的话,就是边为点数-1,如果是有向图呢?除了前面一条还要保证的是必须只有一个根,这个道理很简单,如果非联通图的话生成树是一个森林,当然不行,所以必须保证只有一个根。

很多方案,我都不会,转化为并查集的方案:
1.每来一个条边加入到集合中,最后判断,存在的这些点必须只属于一个集合。(有向图在加入边的时候必须一个固定的加入方向,没有按什么树的深度优化并查集的,否则就错了。) 当然有向图如果一个新的节点指向一个有根的孩子节点,那么就一定不是树了。如果两个节点有同一个根,他们又多了一条边。。这个你懂的。
2.void 也是一个棵树,这个退化情况希望大家可以处理到一般情况中,退化情况如果总是单独处理,只能说明你水平不行,退化情况,一定要统一处理,这样才能化繁为简。

代码:
#include<iostream>
#include
<cstdio>
#include
<map>
using namespace std;
const int maxnum=100000+1;
#define re1(i,n) for(int i=1;i<=(n);++i)
int G[maxnum];
int yank[maxnum];
int find(int x){
    
if(G[x]!=x)
        G[x]
=find(G[x]);
    
return G[x];
}
bool u3n(int a,int b){
    
int x= find(a);
    
int y= find(b);
    
if(x==y)
        
return false;
    
if(yank[x]>yank[y])
        G[y]
=x;
    
else{
        G[x]
=y;
        
if(yank[x]==yank[y])
            yank[y]
++;
    }
    
return true;
}
int main(){
    
int t1,t2,tcase=0;
    
while(scanf("%d%d",&t1,&t2)){
        
if(t1==t2 && t2==-1)
            
break;
        re1(u,maxnum){
            G[u]
=u;
            yank[u]
=0;
        }
        map
<int,int> edge;
        tcase
++;
        
bool flag=true;
        
while(!(t1==t2 && t2==0)){
            edge[t1]
=1;
            edge[t2]
=1;
            
if(!u3n(t1,t2))
                flag
=false;
            scanf(
"%d%d",&t1,&t2);
        }
        
int sum=0;
        re1(u,maxnum){
            
if(edge[u]==1&&G[u]==u)
                sum
++;
        }
        
if(!(sum==0 || sum==1))
            flag
=false;
        
if(flag)
            printf(
"Yes\n");
        
else
            printf(
"No\n");
    }
}

#include<iostream>
#include
<cstdio>
using namespace std;
const int maxnum=100000+10;
#define re1(i,n) for(int i=(1);i<=(n);++i)
template
<class T>
void show(T *a,int n,int m){
    
for(int i=n;i<=m;++i)
        cout
<<a[i]<< ' ';
    cout
<<endl;
}
int G[maxnum];
int yank[maxnum];
int edge[maxnum];
int find(int x){
    
if(G[x]!=x)
        G[x]
=find(G[x]);
    
return G[x];
}
bool u3n(int a,int b){
    
int x= find(a);
    
int y= find(b);
    
if(x==y)
        
return false;
    G[y]
=x;
    
return true;
}
int main(){
//#define home gggin
    #ifdef home
    freopen(
"6.txt","r",stdin);
    
#endif
    
int t1,t2,tcase=0;
    
while(scanf("%d%d",&t1,&t2)){
        
if(t1<0 || t2<0)
            
break;
        re1(u,maxnum
-1){
            G[u]
=u;
            edge[u]
=0;
        }
        tcase
++;
        
bool flag=true;
        
while(!(t1==t2 && t2==0)){
            edge[t1]
=1;
            edge[t2]
=1;

            
if(find(t2)!=t2)
                flag
=false;
            
else if(!u3n(t1,t2))
                flag
=false;

            scanf(
"%d%d",&t1,&t2);


        }
        
//show(G,1,5);
        int sum=0;
        re1(u,maxnum
-1){
            
if(edge[u]&&G[u]==u)
                sum
++;
        }
        
if(!(sum==0 || sum==1))
            flag
=false;
        
if(flag)
            printf(
"Case %d is a tree.\n",tcase);
        
else
            printf(
"Case %d is not a tree.\n",tcase);


    }
}
posted on 2012-12-10 21:50 Gin 阅读(7848) 评论(2)  编辑 收藏 引用 所属分类: Data Structure

FeedBack:
# re: 判断一个图是否是一个树(有向图,无向图)
2014-05-22 13:11 | 郭帅
图为一部分排水管道与进水口抽象成的一个有向连通图,结点表示进水口点,箭头方向表示排水管道排水的走向. 用邻接矩阵 来表示有向图 ,若 与 相邻接,则 ,若 与 不邻接,则 . 为所有结点的集合, 为已找到的结点的序列集合,它的初始状态为空集.
步骤1 选择结点 使得 的出度为0,即 ,令

步骤2 从搜索结点 开始搜索以 为结点的所有前继结点 ,则

步骤3 令 为 序列中 的下一个结点,执行步骤3,直到 的前继结点为空集结点为止.这样,便可得由集合 中的结点构成的一棵树.
  回复  更多评论
  
# re: 判断一个图是否是一个树(有向图)
2014-05-22 13:12 | 郭帅
我有算法,但是不会编程,请教下你  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2012年12月>
2526272829301
2345678
9101112131415
16171819202122
23242526272829
303112345

常用链接

留言簿

随笔分类

随笔档案

friends

  • figoSB
  • 除了我...谁敢叫韩飞sb...

搜索

  •  

最新评论

阅读排行榜

评论排行榜