题目：
http://ac.jobdu.com/problem.php?pid=1481
http://acm.nyist.net/JudgeOnline/problem.php?pid=129
http://poj.org/problem?id=1308
http://acm.hdu.edu.cn/showproblem.php?pid=1272
题目意思就是判断一些给定的支点构成的树是不是一颗合法的树，
判断是不是一颗合法的树如下：
1、该树只有一个根节点
2、不存在环
对于上述两种情况采用如下进行判断：
1、定义一个标识符，当这个点出现，并且父节点和自己相同的节点个数大于1，表示有多个根节点，反之不是
2、在寻找父节点时，这两点指向同一个父节点，则出现了回路
nyoj 和poj 直接使用下代码就ok ，hdu上面相应的改改（代码最后一个）一开始一直RE 后来看看了题目 是10^5,（纠结了）
/*hdu 1272*/
#include<stdio.h>
#include <string.h>
#define N 100005 int f[N];
int a[N];
int flag = 1;
int max = 0; void init()
{
memset(a,0,sizeof(a)); memset(f,0,sizeof(f));
max = 0;
flag = 1;
int i;
for(i = 0; i <= N; i++)
f[i] = i;
}
int find_f(int x)
{
if(x == f[x]) return x;
else
return f[x] = find_f(f[x]);
} void add(int x,int y)
{
int fx = find_f(x);
int fy = find_f(y);
if(fx != fy)
f[fy] = fx;
else flag = 0;
} int main()
{
int x,y;
int fx,fy;
init();
while(1)
{
scanf("%d%d",&x,&y);
if(x == -1 && y == -1) break;
if(x ==0 && y == 0)
{
int t = 0;
if(flag)
{
int i;
for(i = 0; i <= max; i++)
if(a[i] == 1)
{
if(i == f[i]) t++;
}
}
if(t > 1)
flag = 0;
if(flag)
printf("Yes\n");
else
printf("No\n");
init();
}
else
{
if(flag)
{
max = max > (x > y ? x : y) ? max: (x > y ? x : y) ;
add(x,y);
a[x] = 1;
a[y] = 1;
}
}
}
return 0;
}
/***
判断是否有环，当他们的父相同则会出现环，然后是判断是否还有孤立的点（树存在）
*/
#include<stdio.h>
#include <string.h>
#define N 10005 int f[N];
int a[N];
int in[N];
int flag = 1;
int max = 0; void init()
{
memset(a,0,sizeof(a));
memset(in,0,sizeof(in));
memset(f,0,sizeof(f));
max = 0;
flag = 1;
int i;
for(i = 0; i <= N; i++)
f[i] = i;
}
int find_f(int x)
{
if(x == f[x]) return x;
else
return find_f(f[x]);
}
int main()
{
int x,y;
int fx,fy;
init();
int tt = 0;
while(1)
{
scanf("%d%d",&x,&y);
if(x == -1 && y == -1)
break;
if(x == 0 && y == 0)
{
int t = 0,i;
if(flag)
{
for(i = 0; i <= max; i++)
if(a[i] == 1)
{
if(i == f[i]) t++;
}
}
if(t > 1)
flag = 0;
tt++;
if(flag)
printf("Case %d is a tree.\n",tt);
else
printf("Case %d is not a tree.\n",tt); init();
}
else
{
a[x] = 1;
a[y] = 1;
in[y]++;
max = max > (x > y ? x : y) ? max : (x > y ? x : y);
if(in[y] > 1)
{
flag = 0;
}
if(flag == 1)
{
fx = find_f(x);
fy = find_f(y);
//printf("%d %d\n",fx,fy);
if(fx != fy) f[fy] = fx;
else
flag = 0;
} }
}
return 0;
}
最后跟新贴一个javaAC全部的代码
import java.util.Scanner;
//判断是否是树
public class Main {
private static My_Tree[] tree = new My_Tree[10007] ;//定义对象数组保存输入的值
private static boolean Main_flag = false;
private static int t = 1;
public static void init(){
for(int i = 0; i < 10007; i++)
tree[i] =new My_Tree(i,i,0,false);
Main.Main_flag = false;
}
public static int find_f(int x){
if(tree[x].getN() == tree[x].getF())
return tree[x].getF();
else
return find_f(tree[x].getF());
}
public static void main(String[] args) {
Scanner cin = new Scanner(System.in);
int n,m;
Main.init();
while(true){
n = cin.nextInt();
m = cin.nextInt();
// System.out.println(Main.Main_flag);
if(n == -1 && m == -1)
break;
if(n == 0 && m == 0){
int t_tmp = 0;
if(!Main.Main_flag){
for(int i = 0; i < 10007; i++)
if(tree[i].isFlag()){
// tree[i].print();
if(tree[i].getF() == tree[i].getN())
t_tmp++;
}
}
if(t_tmp > 1)
Main.Main_flag = true;
if(!Main.Main_flag)
System.out.println("Case "+(Main.t++)+" is a tree.");
else
System.out.println("Case "+(Main.t++)+" is not a tree.");
Main.init();
}
else{
int fx,fy;
tree[n].setFlag(true);
tree[m].setFlag(true);
tree[m].setIn(tree[m].getIn()+1);
if(tree[m].getIn() > 1)
Main.Main_flag = true;
if(!Main.Main_flag){
fx = Main.find_f(n);
fy = Main.find_f(m);
if(fx != fy)
tree[m].setF(fx);
else
Main.Main_flag = true;
}
}
}
}
}
class My_Tree{
private int n,f,in;
private boolean flag;
public My_Tree(int n, int f, int in, boolean flag) {
super();
this.n = n;
this.f = f;
this.in = in;
this.flag = flag;
}
public My_Tree() {
super();
}
public int getN() {
return n;
}
public void setN(int n) {
this.n = n;
}
public int getF() {
return f;
}
public void setF(int f) {
this.f = f;
}
public int getIn() {
return in;
}
public void setIn(int in) {
this.in = in;
}
public boolean isFlag() {
return flag;
}
public void setFlag(boolean flag) {
this.flag = flag;
}
public void print(){
System.out.println("--->"+n+f+in+flag);
}
}
/**************************************************************
Problem: 1481
User: yangyin1217
Language: Java
Result: Accepted
Time:790 ms
Memory:105768 kb
****************************************************************/