1250: HH的米5【并查集】+【欧拉回路】

╰+攻爆jí腚メ 2022-08-10 10:59 116阅读 0赞

## 1250: HH的米5 ##

时间限制: 1 Sec 内存限制: 128 MB  
提交: 101 解决: 28  
\[ [提交][Link 1]\]\[ [状态][Link 2]\]\[ [讨论版][Link 3]\]

## 题目描述 ##

HH新买了一台手机小米5，他给自己的新手机设置了一个高端大气上档次的屏幕保护锁（其实就是一个9宫锁屏），保护锁有一个特点，就是需要一笔画下来才能解锁，HH就在想，如果给定N个点和M条边，那么该图是否可以通过一笔将该图画下来呢？他想请你帮他写一个程序，判断一个图是否能够用一笔画下来。 规定，所有的边都只能画一次，不能重复画。

## 输入 ##

第一行只有一个正整数T(T<=10)表示测试数据的组数。 每组测试数据的第一行有两个正整数N,M(N<=1000,M<=2000)，分别表示这个画中有多少个顶点和多少条连线。（点的编号从1到N） 随后的M行，每行有两个正整数A,B(0<a,b<n)，表示编号为a和b的两点之间有连线。< p="">

## 输出 ##

如果存在符合条件的连线，则输出"Yes", 如果不存在符合条件的连线，输出"No"。

注意输出不包含引号！

## 样例输入 ##

4 3

1 2

1 3

1 4

4 5

1 2

2 3

1 3

1 4

3 4

## 样例输出 ##

Yes

**欧拉回路：**

**从无向图的一个节点出发走出一条道路，每条边恰好经过一次这样的，这样的道路称为“欧拉回路”(E图)**

**在欧拉道路中“进”，“出”是一一对应的(除了起点和终点之外)，其他点的“**进出”次数应该相等，即除了起点跟终点之外，其他点的度数应该是偶数；

如果一个图是无向连通图，且最多有两个奇点(度数为奇数)，则一定存在欧拉回路，如果有两个奇点，必须从一个奇点出发到另一个奇点结束，如果不存在奇点，则可以从任意的点出发，必存在欧拉回路

对于有向图来说同样最多只能有两个点的出度不等于入度，而且必须把其中一个入度比出度大一的点作为起点，而入度比出度小一的点作为终点，当然忽略图的方向，图必须是连通的

#include<iostream>
    #include<cstring>
    #include<queue>
    #define MAX 1005
    using namespace std;
    int Map[MAX][MAX],visit[MAX];
    int P,Q,con;//con用于记录连通点的个数 
    int Euler(){
    	int cont=0;//统计奇度点的个数 
    	queue<int>q;
    	q.push(1);
    	visit[1]=1;
    	while(!q.empty()){
    		int t=q.front();
    		q.pop();
    		con++;
    		int sum=0;//记录这个点的边数 
    		for(int i=1;i<=P;i++){
    			if(Map[t][i]){
    				if(!visit[i]){
    					visit[i]=1;
    					q.push(i);
    				}	
    				sum++;
    			}
    		}
    		if(sum%2){
    			cont++;
    		}
    	} 
    	return cont;
    }
    int main(){
    	int T; cin>>T;
    	while(T--){
    		cin>>P>>Q;
    		memset(visit,0,sizeof(visit));
    		memset(Map,0,sizeof(Map));
    		con=0;
    		for(int i=0;i<Q;i++){
    			int A,B; cin>>A>>B;
    			Map[A][B]=Map[B][A]=1;
    		}
    		int cont=Euler();
    		if((cont==0 || cont==2) && P==con){
    			cout<<"Yes"<<endl;
    		}
    		else cout<<"No"<<endl;
    	}
    }

[Link 1]: http://122.206.78.33:8080/JudgeOnline/submitpage.php?id=1250
[Link 2]: http://122.206.78.33:8080/JudgeOnline/problemstatus.php?id=1250
[Link 3]: http://122.206.78.33:8080/JudgeOnline/bbs.php?pid=1250