# HDU 1325 Is It A Tree? （POJ 1308）

```#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[10010];
bool vis[10010];
int in[10010];
int father(int x)
{
if(fa[x]!=x)
fa[x]=father(fa[x]);
return fa[x];
}
void intt()
{
for(int i=0;i<=10010;i++)
fa[i]=i,vis[i]=in[i]=0;
}
int main()
{
intt();
int x,y;
bool flag=1;
int tmp=0;
int treecot=1;
while(scanf("%d%d",&x,&y))
{
if(x<0&&y<0)return 0;
tmp=max(tmp,max(x,y));
if(x==0&&y==0)
{
int cot=0;
for(int i=0;i<=tmp;i++)
{
if(vis[i]==1&&father(i)==i)cot++;//非常之坑爹！
if(in[i]>1||cot>1)flag=0;
if(!flag)break;
}
if(flag)printf("Case %d is a tree.\n",treecot++);
else printf("Case %d is not a tree.\n",treecot++);
intt();
flag=1,tmp=0;
}
else
{
if(!flag)continue;
int fx=father(x);
int fy=father(y);
if(fx==fy)flag=0;
else
{
fa[fy]=fx,in[y]++;
vis[x]=vis[y]=1;
}
}
}
}
```

HDU 1325 Is It A Tree? （POJ 1308）,布布扣,bubuko.com

## 【HDU 4408】Minimum Spanning Tree（最小生成树计数）

Problem Description XXX is very interested in algorithm. After learning the Prim algorithm and Kruskal algorithm of minimum spanning tree, XXX finds that there might be multiple solutions. Given an undirected weighted graph with n (1<=n<=100) vertex

## hdu 4670 Cube number on a tree（点分治）

Cube number on a tree Time Limit: 20000/10000 MS (Java/Others)    Memory Limit: 65535/65535 K (Java/Others)Total Submission(s): 1628    Accepted Submission(s): 382 Problem Description The country Tom living in is famous for traveling. Every year, man

## POJ 2367：Genealogical tree（拓扑排序）

Genealogical tree Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 2738 Accepted: 1838 Special Judge Description The system of Martians' blood relations is confusing enough. Actually, Martians bud when they want and where they want. They ga

## HDU 2489 Minimal Ratio Tree（数据结构-最小生成树）

Minimal Ratio Tree Problem Description For a tree, which nodes and edges are all weighted, the ratio of it is calculated according to the following equation. Given a complete graph of n nodes with all nodes and edges weighted, your task is to find a