题目链接

知识点：二分图

题目大意：

给出 n 个点 m 条边 的无向图，给出 k 个点，这 k 个点上每个点都有一个人，每个人每回合能走到一个相邻的节点（不能停留不走），问：有没有可能在某一个回合，让这些人都集中在一个点？

仔细阅读题目过后，先来看看二分图定义：

  二分图又叫二部图,二分图有复杂的百度百科定义，这里给出它的一个等价定义：
  二分图的一个等价定义是：不含有「含奇数条边的环」的图，注意这里不是说该图不含奇数个数的环，而是说该图含有的环里边数不能是奇数。

而再观察该题可知：

  让每个人集中到同一个点，而且每一个回合都需要走。

那么该图里面所有人的奇偶性需要是一样的，这样的话才能保证所有人都到同一个点，如果图里有奇数环（环的边数为奇数的环）,那么奇偶性不同的人可以通过走若干遍这个奇数环就能变成奇偶性相同的（显然成立）

而二分图有个经典算法：染色法判断二分图。
如果说是二分图的话，那么就不含有奇数环，这是二分图的定义。那么对于该题来说，如果是二分图，就需要判断这些人的奇偶性初始时是否一样，如果不一样的话就是无法到达同一点的，因为不含奇数环，所以奇偶性不可改变。 如果不是二分图的话，一定有奇数环，那么一定有解。

下面给出染色法判二分图的步骤：

dfs(当前点,当前颜色)
{
	给当前点染色
	遍历当前点的所有邻接点:
  		如果该点没有染色：
  			那么判断它能不能染成对立的颜色
			{
  				如果不能 return false;
  			}
  		如果该点已经染色：
  			判断颜色是否是当前颜色
  			{
  				if(是) return false;
  			}
  	return true;
}

code:

bool dfs(int u,int c)
{//一般用1代表一种颜色，则3-c代表对立的颜色，很方便
    color[u] = c;//color数组记录每个点的染色情况，这里是给当前点染色为c
    for(int i = h[u];i!=-1;i = ne[i])
    {
        int j = e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c))
            {
                return false;
            }
        }
        else if(color[j]==c)
        {
            return false;
        }
    }
    return true;
}

两种办法解决该题：在知道如何判二分图以后，直接套用模板判二分图，如果是二分图，就可以选取任意有人的一点：
1.通过color数组得到它的染色情况，判断所有人的染色情况是否与它相同，如果相同，则YES。
2.通过bfs得到所有有人的点与该点的距离，判断它们的奇偶性是否相同，如果相同则YES。

第一种ACcode:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int e[N],ne[N],h[N],idx;
int num[N];//表示这个点是否有人
int color[N];
int d[N],q[N];
vector<int>dist;
void add(int a,int b)
{
  e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool dfs(int u,int c)
{//该dfs判二分图
  color[u] = c;
  for(int i = h[u];i!=-1;i = ne[i])
  {
      int j = e[i];
      if(!color[j])
      {
          if(!dfs(j,3-c))
          {
              return false;
          }
      }
      else if(color[j]==c)
      {
          return false;
      }
  }
  return true;
}
int main()
{
  memset(h,-1,sizeof h);
  int n,m,k;
  cin>>n>>m>>k;
  while(m--)
  {
      int a,b;
      cin>>a>>b;
      add(a,b);
      add(b,a);
  }
  for(int i = 0;i<k;i++)
  {
      cin>>num[i];
  }
  bool flag = true;
  for(int i = 1;i<=n;i++)
  {
      if(!color[i])
      {
          if(!dfs(i,1))
          {
              flag = false;
              break;
          }
      }
  }
  if(flag)
  {//说明是二分图，不存在奇数环
      bool flag2 = true;
      int c = color[num[0]];
      for(int i = 1;i<k;i++)
      {
          if(color[num[i]]!=c)
          {
              flag2 = false;
              break;
          }
      }
      if(!flag2)
      {
          cout<<"NO";
      }
      else
      {
          cout<<"YES";
      }
  }
  else
  {//说明不是二分图，一定有奇数环，那么距离的奇偶性一定可以通过奇数环而随意改变
      cout<<"YES";
  }
  return 0;
}

第二种ACCODE:

#include<bits/stdc++.h>
using namespace std;

const int N = 1e6+10;
int e[N],ne[N],h[N],idx;
bool st[N];//表示这个点是否有人
int color[N];
int d[N],q[N];
vector<int>dist;
void add(int a,int b)
{
  e[idx] = b;ne[idx] = h[a];h[a] = idx++;
}
bool dfs(int u,int c)
{//该dfs判二分图
  color[u] = c;
  for(int i = h[u];i!=-1;i = ne[i])
  {
      int j = e[i];
      if(!color[j])
      {
          if(!dfs(j,3-c))
          {
              return false;
          }
      }
      else if(color[j]==c)
      {
          return false;
      }
  }
  return true;
}
void bfs(int start)
{//bfs记录各点到起点start的路径长度
  memset(d,-1,sizeof d);
  q[0] = start;
  int hh = 0,tt = 0;
  d[start] = 0;
  while(hh<=tt)
  {
      auto t = q[hh++];
      for(int i = h[t];i!=-1;i = ne[i])
      {
          int j = e[i];
          if(d[j]==-1)
          {
              d[j] = d[t]+1;
              q[++tt] = j;
          }
      }
  }
}
int main()
{
  memset(h,-1,sizeof h);
  int n,m,k;
  cin>>n>>m>>k;
  while(m--)
  {
      int a,b;
      cin>>a>>b;
      add(a,b);
      add(b,a);
  }
  while(k--)
  {
      int num;cin>>num;st[num] = true;
  }
  bool flag = true;
  for(int i = 1;i<=n;i++)
  {
      if(!color[i])
      {
          if(!dfs(i,1))
          {
              flag = false;
              break;
          }
      }
  }
  if(flag)
  {//说明是二分图，不存在奇数环
      //随便选一个点做dfs记录其他有人的点离该点的距离的奇偶性 如果所有点奇偶性相同，那么就是可以走到
      //同一个点，否则就不行
      int start;
      for(int i = 1;i<=n;i++)
      {
          if(st[i]==true)
          {
              start = i;
              break;
          }
      }
      bfs(start);
      for(int i = 1;i<=n;i++)
      {
          if(st[i])
          {
              dist.push_back(d[i]);
          }
      }
//         for(int i = 0;i<dist.size();i++)
//             cout<<dist[i]<<" ";
//         cout<<endl;
      int num = dist[0]%2;
      bool flag2 = true;
      for(int i = 0;i<dist.size();i++)
      {
          if(dist[i]%2!=num)
          {
              flag2 = false;
              break;
          }
      }
      if(flag2)
      {
          cout<<"YES";
      }
      else
      {
          cout<<"NO";
      }
  }
  else
  {//说明不是二分图，一定有奇数环，那么距离的奇偶性一定可以通过奇数环而随意改变
      cout<<"YES";
  }
  return 0;
}