历年上机题----Is It A Tree?

缺乏、安全感 2023-07-23 06:55 62阅读 0赞

[https://www.nowcoder.com/practice/1c5fd2e69e534cdcaba17083a5c56335?tpId=61&tqId=29506&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking][https_www.nowcoder.com_practice_1c5fd2e69e534cdcaba17083a5c56335_tpId_61_tqId_29506_tPage_1_ru_kaoyan_retest_1002_qru_ta_pku-kaoyan_question-ranking]

保证是一棵树，需要满足以下条件：

1. 只有一个根节点

2. 每个节点只能有一个父亲节点

3. 不能有环

#include <bits/stdc++.h>
    using namespace std;
    const int maxn=1e5+7;
    int main()
    {
        #ifndef ONLINE_JUDGE
            freopen("in.txt","r",stdin);
            freopen("out.txt","w",stdout);
        #endif
        int a,b;
        int T=1;
        int f[maxn];
        set<int> S;
        memset(f,0,sizeof(f));
        while(scanf("%d%d",&a,&b)!=EOF)
        {
            if(a==-1&&b==-1) break;
            if(a==0&&b==0)
            {
                if(S.size()==0)
                {
                    cout<<"Case "<<T<<" is a tree."<<endl;   
                }
                else
                {
                    bool flag=0;
                    int cnt=0;
                    for(auto t:S)
                    {
                        if(f[t]>1)
                        {
                            flag=1;
                            break;
                        }
                        if(f[t]==0)
                        {
                            cnt++;
                        }
                    }
                    if(cnt>1||cnt==0) flag=1;
                    if(flag)
                    {
                        cout<<"Case "<<T<<" is not a tree."<<endl;
                    }
                    else
                    {
                        cout<<"Case "<<T<<" is a tree."<<endl;   
                    }
                }
                T++;
                memset(f,0,sizeof(f));
                S.clear();
            }
            else
            {
                S.insert(a);
                S.insert(b);
                f[b]++;
               // cout<<a<<" "<<b<<endl;
                if(a==b&&a!=0) f[a]++;        
            }
        
        }
        return 0;
    }

[https_www.nowcoder.com_practice_1c5fd2e69e534cdcaba17083a5c56335_tpId_61_tqId_29506_tPage_1_ru_kaoyan_retest_1002_qru_ta_pku-kaoyan_question-ranking]: https://www.nowcoder.com/practice/1c5fd2e69e534cdcaba17083a5c56335?tpId=61&tqId=29506&tPage=1&ru=/kaoyan/retest/1002&qru=/ta/pku-kaoyan/question-ranking