70pts求调
查看原帖
70pts求调
1384158
Alvin0228楼主2024/10/9 22:44
#include<bits/stdc++.h>
using namespace std;
int fa[550005],v[550005];
int find(int x)
{
	if (fa[x]!=x) fa[x]=find(fa[x]);
	return fa[x];
}
void unionn(int r1,int r2)
{
	fa[r2]=r1;
}
unordered_map<string,int> m;
int n=0;
int getid(string s) 
{
    if (m[s]==0)
    {
		n++;
    	m[s]=n;
	}
	return m[s];
}
int main ()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	string s1,s2;
	int cnt=0;
	while (cin>>s1>>s2)
	{
        // if (s1=="0"&&s2=="0") break;
		int x=getid(s1),y=getid(s2);
		if (x!=y) 
        {
            cnt++;
            unionn(x,y);
        }
        v[x]++;
        v[y]++;
	}
    if (n==cnt)
    {
        int cc=0;
        for (int i=1;i<=n;i++)
        {
            if((v[i]&1)&&++cc>2)
            {
                cout<<"Impossible";
                return 0;
            }
        }
        cout<<"Possible";
        return 0;
    }
    cout<<"Impossible";
	return 0;
}
2024/10/9 22:44
加载中...