#include <bits/stdc++.h>
using namespace std;
set<set<int> > independentSets;
set<set<int> > maximalIndependentSets;
map<pair<int, int>, int> edges;
vector<int> vertices;
void printAllIndependentSets()
{
for (auto iter : independentSets) {
cout << "{ ";
for (auto iter2 : iter) {
cout << iter2 << " ";
}
cout << "}";
}
cout << endl;
}
void printMaximalIndependentSets()
{
int maxCount = 0;
int localCount = 0;
for (auto iter : independentSets) {
localCount = 0;
for (auto iter2 : iter) {
localCount++;
}
if (localCount > maxCount)
maxCount = localCount;
}
for (auto iter : independentSets) {
localCount = 0;
set<int> tempMaximalSet;
for (auto iter2 : iter) {
localCount++;
tempMaximalSet.insert(iter2);
}
if (localCount == maxCount)
maximalIndependentSets
.insert(tempMaximalSet);
}
for (auto iter : maximalIndependentSets) {
cout << "{ ";
for (auto iter2 : iter) {
cout << iter2 << " ";
}
cout << "}";
}
cout << endl;
}
bool isSafeForIndependentSet(
int vertex,
set<int> tempSolutionSet)
{
for (auto iter : tempSolutionSet) {
if (edges[make_pair(iter, vertex)]) {
return false;
}
}
return true;
}
void findAllIndependentSets(
int currV,
int setSize,
set<int> tempSolutionSet)
{
for (int i = currV; i <= setSize; i++) {
if (isSafeForIndependentSet(
vertices[i - 1],
tempSolutionSet)) {
tempSolutionSet
.insert(vertices[i - 1]);
findAllIndependentSets(
i + 1,
setSize,
tempSolutionSet);
tempSolutionSet
.erase(vertices[i - 1]);
}
}
independentSets
.insert(tempSolutionSet);
}
int main()
{
int V = 3, E = 0;
for (int i = 1; i <= V; i++)
vertices.push_back(i);
vector<pair<int, int> > inputEdges;
pair<int, int> edge;
int x, y;
for (int i = 0; i < E; i++) {
cout<<i<<endl;
edge.first = inputEdges[i].first;
edge.second = inputEdges[i].second;
edges[edge] = 1;
int t = edge.first;
edge.first = edge.second;
edge.second = t;
edges[edge] = 1;
}
set<int> tempSolutionSet;
findAllIndependentSets(1,
V,
tempSolutionSet);
printAllIndependentSets();
printMaximalIndependentSets();
return 0;
}
What I have tried:
import java.util.*;
public class Globals
{
public static TreeSet<TreeSet<Integer>> independentSets = new TreeSet<TreeSet<Integer>>();
public static TreeSet<TreeSet<Integer>> maximalIndependentSets = new TreeSet<TreeSet<Integer>>();
public static TreeMap<tangible.Pair<Integer, Integer>, Integer> edges = new TreeMap<tangible.Pair<Integer, Integer>, Integer>();
public static ArrayList<Integer> vertices = new ArrayList<Integer>();
public static void printAllIndependentSets()
{
for (var iter : independentSets)
{
System.out.print("{ ");
for (var iter2 : iter)
{
System.out.print(iter2);
System.out.print(" ");
}
System.out.print("}");
}
System.out.print("\n");
}
public static void printMaximalIndependentSets()
{
int maxCount = 0;
int localCount = 0;
for (var iter : independentSets)
{
localCount = 0;
for (var iter2 : iter)
{
localCount++;
}
if (localCount > maxCount)
{
maxCount = localCount;
}
}
for (var iter : independentSets)
{
localCount = 0;
TreeSet<Integer> tempMaximalSet = new TreeSet<Integer>();
for (var iter2 : iter)
{
localCount++;
tempMaximalSet.add(iter2);
}
if (localCount == maxCount)
{
maximalIndependentSets.add(tempMaximalSet);
}
}
for (var iter : maximalIndependentSets)
{
System.out.print("{ ");
for (var iter2 : iter)
{
System.out.print(iter2);
System.out.print(" ");
}
System.out.print("}");
}
System.out.print("\n");
}
public static boolean isSafeForIndependentSet(int vertex, TreeSet<Integer> tempSolutionSet)
{
for (var iter : tempSolutionSet)
{
if (edges.get(new tangible.Pair<auto, Integer>(iter, vertex)) != 0)
{
return false;
}
}
return true;
}
public static void findAllIndependentSets(int currV, int setSize, TreeSet<Integer> tempSolutionSet)
{
for (int i = currV; i <= setSize; i++)
{
if (isSafeForIndependentSet(vertices.get(i - 1), new TreeSet<Integer>(tempSolutionSet)))
{
tempSolutionSet.add(vertices.get(i - 1));
findAllIndependentSets(i + 1, setSize, new TreeSet<Integer>(tempSolutionSet));
tempSolutionSet.erase(vertices.get(i - 1));
}
}
independentSets.add(tempSolutionSet);
}
public static void main(String[] args)
{
int V = 3;
int E = 0;
for (int i = 1; i <= V; i++)
{
vertices.add(i);
}
ArrayList<tangible.Pair<Integer, Integer>> inputEdges = new ArrayList<tangible.Pair<Integer, Integer>>();
tangible.Pair<Integer, Integer> edge = new tangible.Pair<Integer, Integer>();
int x;
int y;
for (int i = 0; i < E; i++)
{
System.out.print(i);
System.out.print("\n");
edge.first = inputEdges.get(i).first;
edge.second = inputEdges.get(i).second;
edges.put(edge, 1);
int t = edge.first;
edge.first = edge.second;
edge.second = t;
edges.put(edge, 1);
}
TreeSet<Integer> tempSolutionSet = new TreeSet<Integer>();
findAllIndependentSets(1, V, new TreeSet<Integer>(tempSolutionSet));
printAllIndependentSets();
printMaximalIndependentSets();
}
}
------------------------------------
public final class Pair<T1, T2>
{
public T1 first;
public T2 second;
public Pair()
{
first = null;
second = null;
}
public Pair(T1 firstValue, T2 secondValue)
{
first = firstValue;
second = secondValue;
}
public Pair(Pair<T1, T2> pairToCopy)
{
first = pairToCopy.first;
second = pairToCopy.second;
}
}