Skip to content

Instantly share code, notes, and snippets.

@thinkphp
Created June 14, 2025 17:17
Show Gist options
  • Save thinkphp/09a05a8773f8045d1d6c480a24f2f7e8 to your computer and use it in GitHub Desktop.
Save thinkphp/09a05a8773f8045d1d6c480a24f2f7e8 to your computer and use it in GitHub Desktop.
Telecommunications Rivalitati
/*
test case 1:
4
0 0 0 1
0 0 1 0
0 1 0 0
1 0 0 0
test case 2:
4
0 1 0 1
1 0 1 0
0 1 0 1
1 0 1 0
Explicatie:
compania 1 este rivala cu companiile 2 si 4
compania 2 este rivala cu companiile 1 si 3
compania 3 este rivala cu companiile 2 si 4
compania 4 este rivala cu companiile 1 si 3
C1 -> C2 --> C1 -->C4 (nu este valida, c1 apare de 2 ori)
C1 -> C3 -> C2 -> C4
verificam 1 - 3 OK;
verificam 3 - 2 RIVAL , nu merge
circular, verificare rivalitati.
Problema 1: Breadth First Search
nodul de start = 4
4
adaugi intr-o coada toti descendentii sai: 4 0 2 5 1 3
*/
#include <stdio.h>
#define SIZE 100
int n;
int adj[SIZE][SIZE];//matricea de rivalitati
int arrangement[SIZE]; //aranjamentul la masa (inloc de culori)
int level, n;
int used[SIZE];//vector pentru a marca companiile folosite
int solution_count = 0; //numarul de solutii gasite
const int MAX_SOLUTIONS = 3;//limita pentru numarul de solutii
int sol() {
return level == n;
}
void init() {
arrangement[level] = 0;
}
int succ() {
if(arrangement[level] < n) {
arrangement[level]++;
return 1;
}
return 0;
}
int valid() {
int current_company = arrangement[level];
//verifica daca compania nu este deja folosita
if(used[arrangement[level]]) {
return 0;
}
if(level == 1) {
return 1;
}
//verificam rivalitatea cu vecinul din stanga
int left_neighbor = arrangement[level-1];
if(adj[current_company][left_neighbor] == 1) return 0;
//pentru ultima pozitie verifica si rivalitatea cu primul (masa circulara)
if(level == n) {
int first_company = arrangement[1];
if(adj[current_company][first_company]) return 0;
}
return 1;
}
void display_solution() {
solution_count++;
printf("Solutia %d: ", solution_count);
for(int i = 1; i <= n; ++i) {
printf("C%d", arrangement[i]);
if(i < n) printf(" -> ");
}
printf(" -> C%d", arrangement[1]);
}
void backtracking() {
int s, v;
level = 1;
while(level > 0 && solution_count < MAX_SOLUTIONS) {
s = 1;
v = 0;
while(s && !v) {
s = succ();
if(s){
v = valid();
}
}
if(s) {
//marcam compania ca fiind folosita
used[arrangement[level]] = 1;
if(sol()) {
display_solution();
//demarcheaza compania pentru urmatoarea incercare
used[arrangement[level]] = 0;
level--;
} else {
level++;
init();
}
} else {
if(level>0){
used[arrangement[level]] = 0;
}
level--;
}
}
}
int main(int argc, char const *argv[]) {
freopen("rivalitati.txt", "r", stdin);
scanf("%d", &n);
printf("Numarul de companii: %d\n", n);
printf("Matricea de rivalitati: \n");
for(int i = 1; i <= n; ++i) {
for(int j = 1; j <= n; ++j) {
scanf("%d", &adj[i][j]);
printf("%d ", adj[i][j]);
}
printf("\n");
}
for(int i = 0; i < n; ++i) used[i] = 0;//initializare vectorul used
printf("Cautam aranjamente valide pentru masa rotunda...\n");
backtracking();
if(solution_count == 0) {
printf("\nNu s-au gasit solutii valide!\n");
} else {
printf("\nS-au gasit %d solutii valide.\n", solution_count);
}
return 0;
}
/*
*/
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment