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