題意是這樣，有一個無向圖，在其中的k個點上有機器人，在每個時刻，機器人移動至與當前節點鄰接的任意一個節點。問有沒有可能在某個時刻所有的機器人移動到一個節點上。
我的思路是這樣的：
在圖連通的情況下，
如果圖中有奇圈，那么任意一個機器人都能夠在偶數步和奇數步內到達任意一個節點，如果所有的機器人都能在偶數步或者奇數步里到達某個節點，那么就成立。因為圖中肯定有2圈，所以先到的機器人總可以用“來回走”的形式等后面的機器人。
這樣，算法就成型了：
1、判斷機器人所在的節點是否連通
2、判斷圖中是否有奇圈（二分圖的定義，只需黑白染色即可判斷）
3、如果有奇圈，則輸出YES，否則，這個圖就是一個二分圖
，所有的機器人都能在偶數步或者奇數步里到達某個節點當且僅當所有的機器人都在同一類節點中。
還有點細節就是編號可能不是1，2，3..N這樣編的，所以要先hash處理下（我偷懶，直接用STL MAP了）
貼代碼
1 # include <cstdio>
2 using namespace std;
3 # define N 105
4 # include <vector>
5 # include <cstring>
6 # include <map>
7 # include <queue>
8 vector<int> g[N];
9 int color[N];
10 int n,k,c;
11 map<int,int> refer;
12 vector<int> ins[N];
13 vector<int> target;
14 bool make_color()
15 {
16 queue<int> q;
17 memset(color,-1,sizeof(color));
18 q.push(target[0]);
19 color[target[0]]=0;
20 while(!q.empty())
21 {
22 int top=q.front(),c=(color[top]?0:1);
23 q.pop();
24 for(int i=0;i<g[top].size();i++)
25 if(color[g[top][i]]==-1)
26 {
27 color[g[top][i]]=c;
28 q.push(g[top][i]);
29 }
30 else if(color[g[top][i]]==color[top])
31 return false;
32 }
33 return true;
34 }
35 bool connect()
36 {
37 queue<int> q;
38 memset(color,-1,sizeof(color));
39 q.push(target[0]);
40 color[target[0]]=0;
41 while(!q.empty())
42 {
43 int top=q.front();
44 q.pop();
45 for(int i=0;i<g[top].size();i++)
46 if(color[g[top][i]]==-1)
47 {
48 color[g[top][i]]=0;
49 q.push(g[top][i]);
50 }
51 }
52 for(int i=0;i<target.size();i++)
53 if(color[target[i]]==-1)
54 return false;
55 return true;
56 }
57 int main()
58 {
59 int testcase;
60 scanf("%d",&testcase);
61 while(testcase--)
62 {
63 c=0;
64 refer.clear();
65 scanf("%d%d",&n,&k);
66 for(int i=0;i<n;i++)
67 {
68 ins[i].clear();
69 int id,num;
70 scanf("%d%d",&id,&num);
71 while(num--)
72 {
73 int t;
74 scanf("%d",&t);
75 ins[i].push_back(t);
76 }
77 refer[id]=c++;
78 }
79 for(int i=0;i<n;i++)
80 {
81 g[i].clear();
82 for(int j=0;j<ins[i].size();j++)
83 g[i].push_back(refer[ins[i][j]]);
84 }
85 target.clear();
86 while(k--)
87 {
88 int t;
89 scanf("%d",&t);
90 target.push_back(refer[t]);
91 }
92 if(!connect())
93 printf("NO\n");
94 else if(!make_color())
95 printf("YES\n");
96 else
97 {
98 bool flag=true;
99 for(int i=1;i<target.size()&&flag;i++)
100 if(color[target[i]]!=color[target[i-1]])
101 flag=false;
102 if(flag) printf("YES\n");
103 else printf("NO\n");
104 }
105 }
106 return 0;
107 }
108