Untitled
unknown
plain_text
3 years ago
1.5 kB
10
Indexable
#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;
}Editor is loading...