题解 | #Is It A Tree?#

Is It A Tree?

http://www.nowcoder.com/practice/1c5fd2e69e534cdcaba17083a5c56335

#include<iostream>
#include<map>
using namespace std;
int main()
{
    int s, e, ss = 0, cnt;
    bool ans = true;
    map<int, int> mp;   //s --> e
    while (cin >> s >> e) {
        if (s == 0 && e == 0) {
            cnt = 0;
            ss++;
            for (auto it : mp) {
                if (it.second == 0) {
                    cnt += 1;
                    if (cnt > 1) {
                        ans = false;
                        break;
                    }
                }
                if (it.second > 1) {
                    ans = false;
                    break;
                }
            }
            if(cnt == 0 && mp.size() == 0)
                ans = true;
            else if(cnt == 0)
                ans = false;
            cout << "Case " << ss << " is " << (ans == false? "not " : "") << "a tree." << endl;
            mp.clear();
            ans = true;
        }
        else {
            if (mp.find(e) == mp.end())
                mp[e] = 1;
            else
                mp[e] += 1;
            if (mp.find(s) == mp.end())
                mp[s] = 0;
            if (s == e)
                ans = false;
        }
    }
}

全部评论

推荐最新楼层

Coming680

楼主

仪陇獭兔养殖技术学校 C++

#include<iostream> #include<vector> #include<map> #include<set> using namespace std; int find(int x,vector<int> &father){ if(x != father[x]) father[x] = find(father[x],father); return father[x]; } void Union(int s,int e,vector<int> &father){ s = find(s,father); e = find(e,father); if(s != e) father[s] = e; } int main() { ios::sync_with_stdio(false); cin.tie(0); int s = 0,e = 0,cnt = 0,num = 0; bool flag = true; vector<int> father; map<int> indegree; set<pair><int> > Set; for(int i = 0;i <= 10000;++i) father.push_back(i); while(s != -1 && e != -1){ while(cin >> s >> e && s && e && s != -1 && e != -1){ if(Set.count(pair<int>(s,e)) == 0) Set.insert(pair<int>(s,e)); else flag = false; } if(s == -1 && e == -1) break; for(auto it : Set){ s = it.first,e = it.second; if(s != 0 || e != 0){ indegree[e]++; if(indegree[e] > 1) flag = false; if(indegree.find(s) == indegree.end()) indegree[s] = 0; Union(s,e,father); } else break; } num++; for(auto it : indegree) if(find(it.first,father) == it.first) cnt++; //排除可能存在的自环 int tag = 0; for(auto it : indegree) if(it.second == 0) tag++; if((cnt > 1 || flag == false || tag == 0 || tag > 1) && !Set.empty()) cout << "Case " << num << " is not a tree." << endl; else cout << "Case " << num << " is a tree." << endl; cnt = 0; father.clear(); for(int i = 0;i <= 10000;++i) father.push_back(i); indegree.clear(); flag = true; Set.clear(); } }</int></int></int></pair></int></int></int></int></set></map></vector></iostream>

题解 | #Is It A Tree?#

全站热榜