題意是這樣，有一個無向圖，在其中的k個點上有機器人，在每個時刻，機器人移動至與當前節(jié)點鄰接的任意一個節(jié)點。問有沒有可能在某個時刻所有的機器人移動到一個節(jié)點上。
我的思路是這樣的：
在圖連通的情況下，
如果圖中有奇圈，那么任意一個機器人都能夠在偶數(shù)步和奇數(shù)步內(nèi)到達任意一個節(jié)點，如果所有的機器人都能在偶數(shù)步或者奇數(shù)步里到達某個節(jié)點，那么就成立。因為圖中肯定有2圈，所以先到的機器人總可以用“來回走”的形式等后面的機器人。
這樣，算法就成型了：
1、判斷機器人所在的節(jié)點是否連通
2、判斷圖中是否有奇圈（二分圖的定義，只需黑白染色即可判斷）
3、如果有奇圈，則輸出YES，否則，這個圖就是一個二分圖
，所有的機器人都能在偶數(shù)步或者奇數(shù)步里到達某個節(jié)點當且僅當所有的機器人都在同一類節(jié)點中。
還有點細節(jié)就是編號可能不是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