Untitled

mail@pastecode.io avatar
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; 
}