posts - 33,  comments - 33,  trackbacks - 0

题意:判断一个给定的图,没有环,而且存在一个链,图上的所有点或者在这条链上或者在其的邻居
题解:
1.判断环:
对于无向图:如果 点 < 边 + 1,则存在环;
然后使用并查集进一步判断环的存在

2.判断是否存在链
首先统计各个点的度,然后对于度为1的点,将其相连的边删掉,再统计新图的度,这时新图应该剩下一条链,
也就是说,新图的不存在大于2个度为1的点,而且这个点在旧图的度是大于1的。

代码:

#include <stdio.h>
#include 
<string.h>
#include 
<vector>
#include 
<queue>

using namespace std;

const int N = 105;

vector
<int> graphs[N];
int deg[N];
int degOld[N];
int n,e;
int cnt;

class UnionSet
{
private:
    
int parent[N];
    
int rank[N];
    
int size;
public:
    UnionSet()
    
{
        size 
= 0;
    }


    UnionSet(
int _size)
    
{
        init(_size);
    }

    
~UnionSet()
    
{

    }


    
void init(int _size)
    
{
        size 
= _size;
        
for (int i = 0; i < size; ++i)
        
{
            parent[i] 
= -1;
            rank[i] 
= 1;
        }

    }


    
void adjust(int _root,int _x)
    
{
        
int i = _x;
        
int j ;
        
while(parent[i] >= 0)
        
{
            j 
= parent[i];
            parent[i] 
= _root;
            i 
= j;
        }

    }


    
int getRoot(int _x)
    
{
        
int r = _x;
        
while(parent[r] >= 0)
        
{
            r
= parent[r];
        }


        
//adjust
        adjust(r,_x);
        
return r;

    }


    
void join(int _r1,int _r2)
    
{
        
if (_r1 == _r2)
        
{
            
return ;
        }

        
int root1 = getRoot(_r1);
        
int root2 = getRoot(_r2);
        
if (root1 == root2)
        
{
            
return ;
        }

        
if (rank[root1] > rank[root2])
        
{
            parent[root2] 
= root1;
            rank[root1] 
+= rank[root2];
        }

        
else
        
{
            parent[root1] 
= root2;
            rank[root2] 
+= rank[root1];
        }


    }


    
int getRank(int _x)
    
{
        
return rank[_x];
    }


}
;

static UnionSet uSet;



void Test()
{
    memset(deg,
0,sizeof(deg));
    
for (int i = 0; i < N; ++i)
    
{
        graphs[i].clear();
    }

    
int a,b;
    uSet.init(n
+1);
    
for (int i = 0; i < e; ++i)
    
{
        scanf(
"%d %d",&a,&b);
        deg[a]
++;
        deg[b]
++;
        graphs[a].push_back(b);
        graphs[b].push_back(a);
        uSet.join(a,b);
    }

    
if (n < e + 1)
    
{
        printf(
"Graph %d is not a caterpillar.\n", cnt);
        
return ;
    }

    
for (int i = 2; i <= n; ++i)
    
{
        
if (uSet.getRoot(1!= uSet.getRoot(i))
        
{
            printf(
"Graph %d is not a caterpillar.\n", cnt);
            
return ;
        }

    }


    
for (int i = 1; i <= n; ++i)
    
{
        degOld[i] 
= deg[i];
    }


    
for (int i = 1; i <= n; ++i)
    
{
        
if (degOld[i] == 1)
        
{
            
for (int j = 0; j < graphs[i].size(); ++j)
            
{
                deg[graphs[i][j]]
--;
            }

        }

    }


    
int tmp = 0;
    
for (int i = 1; i <= n; ++i)
    
{
        
if(degOld[i] > 1 && deg[i] == 1)
            
++tmp;
    }

    
if(tmp > 2)
        printf(
"Graph %d is not a caterpillar.\n", cnt);
    
else
        printf(
"Graph %d is a caterpillar.\n", cnt);

}


int main()
{
    
//freopen("data.txt","r",stdin);
    cnt = 0;
    
while(scanf("%d",&n) != EOF)
    
{
        
if(n == 0)
            
break;
        scanf(
"%d",&e);
        
++cnt;

        Test();
    }

    
return 0;
}


 

posted on 2011-11-17 10:50 bennycen 阅读(5944) 评论(0)  编辑 收藏 引用 所属分类: 算法题解

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