SCHOOLWAY - Đường đến trường

SCHOOLWAY - Đường đến trường

Dữ liệu vào: standard input

Dữ liệu ra: standard output

Giới hạn thời gian: 1.0 giây

Giới hạn bộ nhớ: 128 megabyte

Đăng bởi: middlest

Khu phố Dũng sống có n ngôi nhà được đánh số từ 1 đến n và m con đường nối trực tiếp giữa hai ngôi nhà. Tuy là một học sinh lười biếng nhưng dạo này Dũng rất thích đi học, đơn giản là Dũng vừa tán được một bạn nữ gần nhà nên ngày nào cũng phải chở bạn ấy đến trường. Vì là lần đầu tiên có bạn gái nên Dũng rất cưng chiều bạn mình. Và bạn gái Dũng cũng là một người có sở thích kì lạ: Vào những ngày thứ chẵn (thứ Hai, thứ Tư và thứ Sáu), bạn ấy muốn được đưa đến trường qua một số chẵn các con đường, và ngược lại, vào những ngày thứ lẻ (thứ Ba, thứ Năm, thứ Bảy), bạn ấy lại muốn được đưa đến trường qua một số lẻ các con đường. Đặc biệt, bạn gái của Dũng cho biết rằng nhà bạn ấy không phải là trường, đồng thời có thể đi đến trường theo sở thích của bạn ấy. Yêu cầu này khá khó cho Dũng vì cậu ấy rất lười học và tính toán, nhưng cả nguồn sống của Dũng bỗng chốc thu bé lại vừa bằng một cô gái, Dũng muốn nhờ các bạn NTUCoders giúp đỡ mình xem liệu có thể chở bạn gái đến trường theo sở thích của bạn ấy hay không? Hãy giúp Dũng nhé các bạn!
Dữ liệu vào
Dòng đầu là số T - số lượng test trong file input
T nhóm dòng tiếp theo tương ứng với dữ liệu của T test, có cấu trúc như sau:
Dòng thứ nhất ghi 2 số n và m
m dòng tiếp theo, mỗi dòng ghi 2 số u và v với ý nghĩa có đường nối trực tiếp giữa 2 ngôi nhà u và v
Dữ liệu ra
Gồm T dòng, mỗi dòng tương ứng với kết quả của một test: Xuất ra YES nếu tồn tại ít nhất một cách chở bạn gái của Dũng theo sở thích của bạn ấy và NO trong trường hợp ngược lại (trong trường hợp này bạn gái Dũng đã nói dối )
Giới hạn
T <= 100
1 <= n, m <= 10⁴

Ví dụ

• input
  1
  8 10
  1 2
  1 3
  1 4
  1 5
  1 6
  1 7
  1 8
  2 3
  2 4
  2 5
  output
  YES
  /**************/
   #include <bits/stdc++.h>
  
  using namespace std;
  
  long n, m, T;
  int s;
  int trace[10007];
  vector <int>a[10007];
  void DFS(int u, int v)
  {
      trace[u]=v;
      for(int i=0; i<a[u].size(); i++)
      {
          int j=a[u][i];
          if(trace[j]) s|= trace[j]==v;
          else DFS(j,3-v);
      }
  }
  int main()
  {
      cin>>T;
      while(T--)
      {
          cin>>n>>m;
          int x,y;
          for(int i=1; i<=n; i++)a[i].clear(),trace[i]=0;
          for(int i=1; i<=m; i++)
          {
              cin>>x>>y;
              a[x].push_back(y);
              a[y].push_back(x);
          }
          s=0;
          for(int i=1; i<=n; i++)
          {
              if(!trace[i])
              DFS(i,1);
          }
          cout<<(s ? "YES" : "NO")<<endl;
  
      }
      return 0;
  }