Untitled
unknown
plain_text
6 months ago
1.5 kB
1
Indexable
Never
#include <stdio.h> /*--------------------Init Variable----------------------*/ int Answer; int num_node; int a,b; int matrix[1002][1002]; int count[1002]; int visit[1002]; /*--------------------Init BFS-----------------------------*/ int start, end; int Queue[9999999]; bool isEmpty(){ return start == end; } int Pop(){ int temp = Queue[start]; start++; return temp; } void Push(int node){ Queue[end++] = node; } bool BFS(int node){ for(int i = 1; i <= num_node;i++) visit[i] = 0; start = end = 0; Push(node); visit[node] = 1; int curr; while (!isEmpty()) { curr = Pop(); for(int i = 0; i < count[curr]; i++){ if(visit[matrix[curr][i]] == 1) return true; Push(matrix[curr][i]); visit[matrix[curr][i]] = 1; } } return false; } int main(void) { int test_case; int T; int Answer; freopen("input.txt", "r", stdin); setbuf(stdout, NULL); scanf("%d", &T); for (test_case = 1; test_case <= T; ++test_case) { Answer = 0; scanf("%d",&num_node); for(int i = 1; i <= num_node;i++) count[i] = 0; for(int i = 1; i <= num_node;i++){ scanf("%d",&a); for(int j = 0; j < a; j++){ scanf("%d",&b); matrix[b][count[b]++] = i; } } for(int i = 1; i <= num_node; i++){ if(BFS(i)){ Answer = 1; break; } } if(Answer == 1) printf("Case #%d\nYes\n", test_case); else printf("Case #%d\nNo\n", test_case); } return 0; }