1 #include <algorithm> 2 #include <cstring>  3 #include <cstdio> 4 #include <queue> 5  6 using namespace std; 7  8 const int N(100005); 9 queue<int>que;10 int col[N];11 int n,m,u,v;12 int head[N],sumedge;13 struct Edge14 {15     int to,next;16     Edge(int to=0,int next=0) :17         to(to),next(next){}18 }edge[N<<1];19 20 void ins(int from,int to)21 {22     edge[++sumedge]=Edge(to,head[from]);23     head[from]=sumedge;24 }25 26 int main()27 {28     scanf("%d%d",&n,&m);29     for(;m;m--)30     {31         scanf("%d%d",&u,&v);32         ins(u,v); ins(v,u);33     }34     memset(col,-1,sizeof(col));35     que.push(1);36     col[1]=0;37     while(!que.empty())38     {39         int x=que.front();40         que.pop();41         for(int i=head[x];i;i=edge[i].next)42         {    v=edge[i].to;43             if(col[v]!=-1)44             {45                 if(col[v]==col[x])46                 {47                     printf("Wrong!\n");48                     return 0;49                 }50             }51             else52             {53                 col[v]=col[x]^1;54                 que.push(v);;55             }    56         }57     }58     printf("YES!\n");59     return 0;60 }

 1 #include <cstdio> 2  3 using namespace std; 4  5 const int N(100005); 6 int n,m,u,v; 7 int fa[N<<1]; 8  9 int find(int x)10 {11     return fa[x]==x?x:fa[x]=find(fa[x]);12 }13 14 int main()15 {16     scanf("%d%d",&n,&m);17     for(int i=1;i<=n*2;i++) fa[i]=i;18     for(;m;m--)19     {20         scanf("%d%d",&u,&v);21         int fx=find(u*2-1),fy=find(v*2);22         fa[fx]=fy;23         fx=find(u*2); fy=find(v*2-1);24         fa[fy]=fx;25     }26     for(int i=1;i<=n;i++)27         if(find(i*2)==find(i*2-1))28         {29             printf("Wrong!\n");30             return 0;31         }32     printf("YES!\n");33     return 0;34 }