// Walter Kosters, 21 januari 2008
// Vind aantal elementen van samenhangscomponent van de "puzgraph":
// Gegeven een samenhangende graaf met knopen genummerd
// 0,1,2,3,...,aantal_knopen-1
// nu mag steeds 0 van plaats wisselen met een aangrenzende knoop
// hoeveel samenhangscomponenten levert dit?
// Wilson's tricky six puzzle heeft er 6, zie
//   http://mathworld.wolfram.com/Puz-Graph.html
// Invoergraaf: aantal_knopen aantal_takken v11 v12 ... vk1 vk2
// met k = aantal_takken; eerste tak gaat tussen knopen v11 en v12, etc.
// Voorbeeld (een driehoek):
// 3 3
// 1 2 2 3 3 4
// Compileren: g++ -Wall -o puzgraph puzgraph.cc
// Aanroepen:  ./puzgraph
//

#include <iostream>
#include <fstream>
#include <string>
#include <cstdlib>
using namespace std;

const int MAX = 20;  // maximaal aantal knopen van de graaf

class vakje {
  public:
    vakje* volgende;
    int labels[MAX];
    int plaats0;
};//vakje

class Graaf {
  public:
    int knopen;
    int takken;
    int inhoud[MAX][MAX];
    void leesgraaf ( );
    void loop ( );
};//Graaf

// bereken n!
int fac (int n) {
  int res = 1, i;
  for ( i = 1; i <= n ; i++ )
    res *= i;
  return res;
}//fac

// lees graaf in vanuit file
void Graaf::leesgraaf ( ) {
  int een, twee, i, j;
  string filenaam;
  ifstream infile;
  cout << "Filenaam .. ";
  cin >> filenaam;
  infile.open (filenaam.c_str ( ),ios::in);
  for ( i = 0; i < MAX; i++ )
    for ( j = 0; j < MAX; j++ )
      inhoud[i][j] = false;
  infile >> knopen >> takken;
  if ( knopen > MAX )
    exit (1);
  for ( i = 0; i < takken; i++ ) {
    infile >> een >> twee;
    inhoud[een-1][twee-1] = inhoud[twee-1][een-1] = true;
  }//for
  infile.close ( );
}//Graaf::leesgraaf

// het eigenlijke werk
void Graaf::loop ( ) {
  int i, j, teller = 0;
  bool hetzelfde;
  vakje* loper;
  vakje* laatste;
  vakje* nieuw;
  vakje* check;
  vakje* ingang = new vakje;  // voor de beginpositie
  ingang->volgende = NULL;
  for ( i = 0; i < knopen; i++ )
    ingang->labels[i] = i;
  ingang->plaats0 = 0;
  laatste = ingang;
  loper = ingang;
  while ( loper != NULL ) {
    for ( i = 0; i < knopen; i++ ) {
      if ( inhoud[loper->plaats0][i] ) {  // i kan verschoven worden
        nieuw = new vakje;
	for ( j = 0; j < knopen; j++ )
	  nieuw->labels[j] = loper->labels[j];
	nieuw->volgende = NULL;
	nieuw->plaats0 = i;
	nieuw->labels[loper->plaats0] = loper->labels[i];
	nieuw->labels[i] = 0;
        check = ingang;
	hetzelfde = false;
	while ( check != NULL && ! hetzelfde ) {  // al eerder geweest?
          hetzelfde = true;
          for ( j = 0; j < knopen; j++ )
	    if ( check->labels[j] != nieuw->labels[j] )
	      hetzelfde = false;
          check = check->volgende;
	}//while
	if ( hetzelfde ) {
          delete nieuw;
	  nieuw = NULL;
	}//if
        else {
          laatste->volgende = nieuw;
	  laatste = nieuw;
	}//else
      }//if
    }//for
    loper = loper->volgende;
    teller++;
  }//while
  cout << teller << " element(en)" << endl
       << fac (knopen) / teller << " samenhangscomponent(en)" << endl;
}//Graaf::loop

int main ( ) {
  Graaf G;
  G.leesgraaf ( );
  G.loop ( );
  return 0;
}//main