Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // socialadvertising
- //
- // Created by David Benitez on 5/2/15.
- // Copyright (c) 2015 David Benitez. All rights reserved.
- //
- #include <stdio.h>
- int matriz[20][20];
- int minim;
- bool arr[20];
- void resetMatriz(int x){
- for(int i = 0; i < x; i++){
- for(int j = 0; j < x; j++){
- if(i == j){
- matriz[i][j] = 1;
- }
- else{
- matriz[i][j] = 0;
- }
- }
- }
- }
- void resetArr(int x){
- for(int i = 0; i < x; i++){
- arr[i] = false;
- }
- }
- void metodo(int userNumber, int nivel, int nodo, int acum){
- if(nivel == 1){
- resetArr(userNumber);
- }
- if(nivel < minim){
- for(int i = 0; i < userNumber; i++){
- if(matriz[nodo-1][i] == 1 && !arr[i]){
- arr[i] = true;
- acum++;
- }
- }
- if(acum == userNumber){
- minim = nivel;
- //return minim;
- }
- else{
- int k = nodo;
- while(nivel < minim && k <= userNumber){
- metodo(userNumber, nivel+1, nodo+1, acum);
- k++;
- }
- }
- }
- //return minim;
- }
- using namespace std;
- int main() {
- int testCases, userNumber, a, numAmigos;
- scanf("%d", &testCases);
- for(int i = 0; i < testCases; i++){
- scanf("%d", &userNumber);
- resetMatriz(userNumber);
- for(int j = 0; j < userNumber; j++){
- scanf("%d", &numAmigos);
- for(int k = 0; k < numAmigos; k++){
- scanf("%d", &a);
- matriz[j][a-1] = 1;
- }
- }
- minim = userNumber;
- metodo(userNumber ,1, 1, 0);
- printf("%d\n", minim);
- }
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement