[POJ 2513]&[欧拉路模板] Colored Sticks

一、题目

点此看题

二、解法

这道题是欧拉路的模板题，我们借此对欧拉路做一个具体的梳理。

欧拉回路

欧拉回路指要访问完每条边，要求回到终点的路径。

如果一个无向连通图存在欧拉回路，那么每个点的度数都为偶数（进了就可以立即出去，最后回到起点）

如果一个有向联通图存在欧拉回路，那么每个点的入度等于出度。

欧拉路径

欧拉路径指要访问完每条边，不要求回到终点的路径。

如果一个无向连通图存在欧拉路径，那么只有$0$或$2$个点度数为奇数。

如果一个有向联通图存在欧拉路径，那么只有$0$或$1$个点的入度等于出度加一，只有$0$或$1$个点的入度等于出度减一，其余点的入度都等于出度。

#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
const int M = 500005;
int read()
{
    int x=0,f=1;char c;while((c=getchar())<'0' || c>'9') {
    if(c=='-') f=-1;}while(c>='0' && c<='9') {
    x=(x<<3)+(x<<1)+(c^48);c=getchar();}return x*f;
}
int n,a1,a2,fa[M],num[M];
char s1[15],s2[15];map<string,int> mp;
int find(int x)
{
    if(fa[x]!=x) fa[x]=find(fa[x]);return fa[x];
}
void uni(int u,int v)
{
    int x=find(u),y=find(v);if(x==y) return ;fa[x]=y;
}
signed main()
{
    for(int i=1;i<=5e5;i++)fa[i]=i;while(~scanf("%s %s",s1,s2)){
    if(!mp[s1]) mp[s1]=++n;if(!mp[s2]) mp[s2]=++n;int t1=mp[s1],t2=mp[s2];uni(t1,t2);num[t1]++;num[t2]++;}for(int i=1;i<=n;i++){
    if(i==find(i)) a1++;if(num[i]%2) a2++;}if(!n || (a1==1 && (a2==0 || a2==2)))puts("Possible");//注意n=0 elseputs("Impossible");
}