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