这个题和小希的迷宫很相似但是差一些 有向图和无向图
因为如果是一棵树 根只能有一个 因为是有向图 根肯定是最上面的 它的入度是0 这样的点只能有一个
不能有环
#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
using namespace std;
int fa[100050];
int vis[100050];
int ru[100050];
int chu[100050];
bool ok;
void init()
{
for(int i=0;i<100040;i++)
{
fa[i]=i;
vis[i]=0;
ru[i]=0;
chu[i]=0;
}
ok=true;
}
int find(int i)
{
return fa[i]==i?i:find(fa[i]);
}
void un(int a,int b)
{
int aa=find(a);
int bb=find(b);
if(aa==bb)
ok=false;
else
fa[aa]=bb;
return ;
}
int main()
{
int t=0;
int a,b;
while(~scanf("%d%d",&a,&b))
{
if(a<0&&b<0)
break;
t++;
init();
if(a==0&&b==0)
printf("Case %d is a tree.
",t);
else
{
un(a,b);
vis[a]=1;
vis[b]=1;
chu[a]++;
ru[b]++;
while(~scanf("%d%d",&a,&b))
{
if(a==0&&b==0)
break;
un(a,b);
vis[a]=1;
vis[b]=1;
chu[a]++;
ru[b]++;
}
int ma=0;
int yi=0;
int er=0;
for(int i=0;i<100040;i++)
{
if(vis[i]==1)
{
if(fa[i]==i)
{
ma++;
}
if(ru[i]==0)
{
yi++;
}
}
}
if(ma==1&&yi==1&&ok==true)
printf("Case %d is a tree.
",t);
else printf("Case %d is not a tree.
",t);
}
}
}