rt

这一版代码只能得 70pts WA on #5,6,9

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int tot,cnt,sum;
string s,t;
unordered_map<string,int> deg;
unordered_map<string,string> fa;
string find(string x){
    if (fa[x]==x){
        return x;
    }
    fa[x]=find(fa[x]);
    return fa[x];
}

int main (){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> s >> t){
        if (fa[s]==""){
            fa[s]=s;
            tot++;
        }
        if (fa[t]==""){
            fa[t]=t;
            tot++;
        }
        if (deg[s]%2) cnt--;
        else cnt++;
        if (deg[t]%2) cnt--;
        else cnt++;
        deg[s]++,deg[t]++;
        if (find(s)!=find(t)){
            sum++;
            fa[find(t)]=find(s);
        }
    }
    if ((cnt!=0&&cnt!=2)||(tot!=0&&sum!=tot-1)) cout << "Impossible" << endl;
    else cout << "Possible" << endl;
    return 0;
}

但是，将加度数的操作分开就能 AC。如下

#include <iostream>
#include <string>
#include <unordered_map>
using namespace std;

int tot,cnt,sum;
string s,t;
unordered_map<string,int> deg;
unordered_map<string,string> fa;
string find(string x){
    if (fa[x]==x){
        return x;
    }
    fa[x]=find(fa[x]);
    return fa[x];
}

int main (){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    while (cin >> s >> t){
        if (fa[s]==""){
            fa[s]=s;
            tot++;
        }
        if (fa[t]==""){
            fa[t]=t;
            tot++;
        }
        if (deg[s]%2) cnt--;
        else cnt++;
        deg[s]++;
        if (deg[t]%2) cnt--;
        else cnt++;
        deg[t]++;
        if (find(s)!=find(t)){
            sum++;
            fa[find(t)]=find(s);
        }
    }
    if ((cnt!=0&&cnt!=2)||(tot!=0&&sum!=tot-1)) cout << "Impossible" << endl;
    else cout << "Possible" << endl;
    return 0;
}

求大佬解答