P1333 瑞瑞的木棍

将每个颜色看成点，将小木棒看成边，如果能连成，即为一笔画问题。

首先要注意判断图是否连通，然后统计奇点个数。

注意map的一个优化！！

未优化（90pts T一个点）

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
const int N=500005;
map<string,int> mp;
struct node{
	int to,next;
}edge[N];
int cnt,tot;
int deg[N];
bool vis[N];
int head[N];
string x,y;
int ji,ou;
void add(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u){
	vis[u]=1;
	if(deg[u]&1) ji++;
	else ou++;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(vis[v]) continue;
		dfs(v);
	}
}
int main(){
	for(int i=1;i<=N;i++) head[i]=-1;
	while(cin>>x>>y){
		if(!mp[x]){
			mp[x]=++cnt;
		}
		if(!mp[y]){
			mp[y]=++cnt;
		}
		add(mp[x],mp[y]); add(mp[y],mp[x]);
		deg[mp[x]++; deg[mp[y]++;
	}
	for(int i=1;i<=cnt;i++){
		if(!vis[i]){
			if(i!=1){
				printf("Impossible");
				return 0;
			} 
			ji=0; ou=0;
			dfs(i);
			if(ji!=0&&ji!=2){
				printf("Impossible");
				return 0;
			}
		}
	}
	printf("Possible");
	return 0;
}

优化：

#include<cstdio>
#include<iostream>
#include<map>
#include<cstring>
using namespace std;
const int N=500005;
map<string,int> mp;
struct node{
	int to,next;
}edge[N];
int cnt,tot;
int deg[N];
bool vis[N];
int head[N];
string x,y;
int ji;
void add(int u,int v){
	edge[tot].to=v;
	edge[tot].next=head[u];
	head[u]=tot++;
}
void dfs(int u){
	vis[u]=1;
	if(deg[u]&1) ji++;
	for(int i=head[u];i!=-1;i=edge[i].next){
		int v=edge[i].to;
		if(vis[v]) continue;
		dfs(v);
	}
}
int main(){
	for(int i=1;i<=N;i++) head[i]=-1;
	while(cin>>x>>y){
		int &mx=mp[x],&my=mp[y];
		if(!mx){
			mx=++cnt;
		}
		if(!my){
			my=++cnt;
		}
		add(mx,my); add(mx,my);
		deg[mx]++; deg[my]++;
	}
	for(int i=1;i<=cnt;i++){
		if(!vis[i]){
			if(i!=1){
				printf("Impossible");
				return 0;
			}
			ji=0;
			dfs(i);
			if(ji!=0&&ji!=2){
				printf("Impossible");
				return 0;
			}
		}
	}
	printf("Possible");
	return 0;
}