Solution Kattis: Accomplices

Date	Problem	Judgement	Runtime	Language	Test cases
	23:49:18	Challenge / Accomplices	Accepted	0.16 s	C++	46/46

 Idea: Simple backtracking have check condition

  

#include<bits/stdc++.h>

using namespace std;

int n, m;

int friends[22][22];

vector<int> group;

bool checkGroup(int i){

for(auto x:group)

if (friends[x][i] || x == i) return false;

return true;

}

int addGroup(int x, int sizeGroup){

if (group.size() == sizeGroup){

return 1;

}

int r = 0;

for(int i= x+1; i<=n; i++)

if (checkGroup(i)){

group.push_back(i);

r += addGroup(i, sizeGroup);

group.pop_back();

}

return r;

}

int main(){

cin >> n >> m;

for(int i=1; i<=m; i++){

int u,v; cin >> u >> v;

friends[u][v] = friends[v][u] = true;

}

cout<<1<<" ";

for(int i=1; i<=n; i++){

cout<< addGroup(0, i) << " ";

}

}