sss - NDDCoder

Fork

#include<iostream>
using namespace std;
int index = 1;
int N;
int adjV[1005][1005];
int matrix[1005][1005];
int Queue[1000000];
int top = 0, low = 0;
void push(int val){
	Queue[++top] = val;
}
int pop(){
	return Queue[++low];
}
bool isEmpty(){
	return low == top;
}
int Way[1005][1005];
int visisted[1005];
int cnt[1005];
int path[1005];
bool BFS(int start){
	low = top =0;
	path[start] = -1;
	push(start);
	visisted[start] = index;
	cnt[start] = index;
	while(!isEmpty()){
		int curr = pop();
		int numV = adjV[curr][0];
		for(int i=1;i<=numV;i++){
			int ke = adjV[curr][i];
			if(visisted[ke]==index&&matrix[curr][ke]){
				if(Way[curr][i]!=index){
					cnt[ke]++;
				}
				else{
					continue;
				}
			}
			else if(visisted[ke]!=index&&matrix[curr][ke]){
				//neu chua tham va co duong di tu curr den i(next)
				push(ke);
				visisted[ke] = index;
				cnt[ke] = index;
				Way[ke][curr] = index;
			}
			if(cnt[ke]>=index+1){
				return true;
			}
		}
	}
	return false;
}
int main(int argc, char** argv)
{
	int test_case;
	int T;
	int Answer;
	ios::sync_with_stdio(false);
	freopen("input.txt", "r", stdin);
	cin >> T;
	for(test_case = 1; test_case <= T; ++test_case)
	{
		cin>>N;
		for(int i=1;i<=N;i++){
			for(int j=1;j<=N;j++){
				matrix[i][j] = 0;
				Way[i][j] = 0;	
			}
		}
		for(int i=1;i<=N;i++){
			visisted[i] = 0;
			cnt[i] = 0;
			int numAdjV;
			cin>>numAdjV;
			adjV[i][0] = numAdjV;
			for(int j=1;j<=numAdjV;j++){
				cin>>adjV[i][j];
				matrix[i][adjV[i][j]] = 1;
			}
		}
		int flag = false;
		for(int i=1;i<=N;i++){
			flag = BFS(i);
			index++;
			if(flag==true){
				break;
			}
		}
		cout << "Case #" << test_case <<endl;
		if(flag==true) cout<<"Yes"<<endl;
		else cout<<"No"<<endl;
	}
	return 0;
}