| ||||||||||
| Online Judge | Problem Set | Authors | Online Contests | User | ||||||
|---|---|---|---|---|---|---|---|---|---|---|
| Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest | |||||||||
dfs,0ms秒杀,附代妈#include <iostream>
#include <stdio.h>
#include <map>
using namespace std;
const int OU = 0, JI = 1;
int adjNo[105] = {0};
int adjList[105][105];
void dfs(int cur, bool *jiused, bool *ouused, int jiou){
if(jiou == OU){
ouused[cur] = 1;
for(int i = 0; i < adjNo[cur]; i++){
if(jiused[adjList[cur][i]]) continue;
dfs(adjList[cur][i], jiused, ouused, JI);
}
}
else{
jiused[cur] = 1;
for(int i = 0; i < adjNo[cur]; i++){
if(ouused[adjList[cur][i]]) continue;
dfs(adjList[cur][i], jiused, ouused, OU);
}
}
}
int main() {
int T;
scanf("%d", &T);
for(int ii = 0; ii < T; ii++){
int N, K;
scanf("%d%d", &N, &K);
map<int, int> bh;
int cnt = 0;
for(int i = 0; i < N; i++) adjNo[i] = 0;
for(int i = 0; i < N; i++){
int x, n, bhx;
scanf("%d%d", &x, &n);
if(bh.find(x) == bh.end()){
bhx = cnt;
bh.insert(pair<int, int>(x, cnt));
cnt++;
}
else{
bhx = bh[x];
}
adjNo[bhx] = n;
for(int j = 0; j < n; j++){
int id;
scanf("%d", &id);
int bhid;
if(bh.find(id) == bh.end()){
bhid = cnt;
bh.insert(pair<int, int>(id, cnt));
cnt++;
}
else{
bhid = bh[id];
}
adjList[bhx][j] = bhid;
}
}
int robotList[105];
for(int i = 0; i < K; i++){
int tmp;
scanf("%d", &tmp);
robotList[i] = bh[tmp];
}
if(K == 1){
printf("YES\n");
continue;
}
bool jiused[105] = {0}, ouused[105] = {0};
dfs(robotList[0], jiused, ouused, OU);
bool ok = 1;
for(int i = 1; i < K; i++){
if(!ouused[robotList[i]]){
ok = 0;
break;
}
}
if(ok) printf("YES\n");
else printf("NO\n");
}
return 0;
}
Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator