Coach


From: DHUOJ, 2016060703
<button class="btn btn&#45;default" id="submit&#95;open&#95;top" type="button"> Submit</button>
&amp;lt;a type=&quot;button&quot; class=&quot;btn btn-warning&quot; href=&quot;/solution/submit.html?problemId=5270&quot;&amp;gt;Submit&amp;lt;/a&amp;gt;
<center> Time Limit: 1 s </center>

Description

In the ACM training team, the coach wants to split all students into many groups and each group consists of three students. Let's assume that all students are numbered from 1 1 to n n. The teacher wants the groups to achieve good results, so he wants to hold the following condition: In a group of three students, they are friends. Also it is obvious that each student must be in exactly one team. If A A and B B are friends, B B and C C are friends, then A A and C C are friends.

 

Input

There are multiple test cases.

For each test case, the first line contains integers n n and m m (1≤n≤5000,0≤m≤5000) (1≤n≤5000,0≤m≤5000). Then follows m m lines, each contains a pair of integers a i ,b i  ai,bi (1≤a i ,b i ≤n) (1≤ai,bi≤n). The pair a i ,b i  ai,bi means that the students a i  ai and b i  bi are friend. It is guaranteed that each pair of a i  ai and b i  bi occurs in the input at most once.

 

Output

If the required group division plan doesn't exist, print “No”. Otherwise, print “Yes”.

 

Sample Input 

3 0
6 4
1 2
2 3
4 5
5 6

 

Sample Output 

No
Yes

 

Author: betty


思路：

每三个人组成一组，要求他们三个要有相同的父亲。求能否正好分成若干组，无剩余的人。

经典的并查集问题，因为每个人都会有一个父亲，也就是说，有几种父亲就代表了几个团体，然后就看每个团体里面是否正好是3n个人，若不是，则不能构成。


代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<stack>
using namespace std;
 
int  pre[5050];  
int t[5050]={0};           
int find(int x)  
{  
    int r=x;  
    while(r!=pre[r])  
        r=pre[r];  
       
    int i=x,j;  
    while(pre[i]!=r)  
    {  
        j=pre[i];  
        pre[i]=r;  
        i=j;  
    }  
    return r;  
}  
   
void merge(int x,int y)  
{  
    int fx=find(x),fy=find(y);  
    if(fx!=fy)  
    {  
        pre[fy]=fx;  
    }  
}   
 
int main()  
{  
    int n,m;
    while(~scanf("%d%d",&n,&m)){
        memset(pre,0,sizeof(pre));
        bool flag=1;
        for(int i=1;i<=n;i++){
            pre[i]=i;
        }
        for(int i=0;i<m;i++){
            int a,b;
            scanf("%d%d",&a,&b);
            merge(a,b);
        }
        memset(t,0,sizeof(t));  
        for(int i=1;i<=n;i++)   
        {  
            t[find(i)]++;
        }  
                  
        for(int i=1;i<=n;i++)   
        {  
//              cout<<i<<" "<<t[find(i)]<<" "<<find(i)<<" "<<endl;
            if(t[find(i)]%3!=0){
                flag=0;
                break;
            }  
        }
        if(flag==1)cout<<"Yes"<<endl;
        else cout<<"No"<<endl;  
    }  
 
    return 0;  
}