Biura
Kod był wyświetlany 1577 razy.
    /*
  Name: Biura
  Copyright: GPL GNU
  Date: 	24-01-2007 18:19:09
  Description: 
 etap OI. Zadanie Biura.


Algorytm sprowadza się do znalezienia największych rozłšcznych
grup wierzchołków, w których każdy z wierzchołków
nie sąsiaduje chociaż z jednym z pozostałych.
Liczba tych grup to wła?ie liczba biur. 

Problem ten można byłoby zapewne rozwišzać w dużo bardziej
optymalny sposób niż zaprezentowany poniżej, ale tworzšc
ten algorytm nie znałem jeszcze teorii grafów =) */

#include <cstdio>
int main()
{
	struct Numer //struktura przechowywujšca numer sąsiadującego wierzchołka
	{				
		int cel;	
		Numer *next;
	};
	struct Lista //struktura przechowywujšca ogon i głowę listy
	{
		Numer *glowa;
		Numer *ogon;
	};
	long int n,m,a,b;
	scanf("%d", &n);
	scanf("%d", &m);
	Lista *tabela=new Lista[n];
	for(int i=0;i<n;i++)		//wyzerowanie wska?ika głowa dla każdego wierzchołka
		tabela[i].glowa=NULL;
	for(long int i=0;i<m;i++)	//wczytanie danych
	{
		scanf("%d", &a);
		scanf("%d", &b);
		if(tabela[a-1].glowa==NULL)
		{
			tabela[a-1].glowa=new Numer;
			tabela[a-1].ogon=tabela[a-1].glowa;
		}
		else
		{
			tabela[a-1].ogon->next=new Numer;
			tabela[a-1].ogon=tabela[a-1].ogon->next;
		}
		tabela[a-1].ogon->cel=b-1;
		tabela[a-1].ogon->next=NULL;
		if(tabela[b-1].glowa==NULL)
		{
			tabela[b-1].glowa=new Numer;
			tabela[b-1].ogon=tabela[b-1].glowa;
		}
		else
		{
			tabela[b-1].ogon->next=new Numer;
			tabela[b-1].ogon=tabela[b-1].ogon->next;
		}
		tabela[b-1].ogon->cel=a-1;
		tabela[b-1].ogon->next=NULL;
	}
	bool *matryca=new bool[n];
	Numer *finder=tabela[0].glowa;
	while(finder!=NULL)		//przepisanie listy incydencji pierwszego 
                            //wierzchołka na matrycę
	{
		matryca[finder->cel]=true;
		finder=finder->next;
	}

	for(int k=0;k<n;k++)		//wła?iwa pętla wykonujšca algorytm (ale póki 
                                //co tylko dla 1 wierzchołka!)
	{
		if(matryca[k]==true)	//będziemy zajmować się tylko nie sšsiadujšcymi 
                                //wierzchołkami
		{
                         continue;
        	}
		finder=tabela[k].glowa;
		
		int *pomoc=new int[n];	
		while(finder!=NULL)	//przepisanie listy incydencji wierzchołka k na pomoc
		{
			pomoc[finder->cel]=1;
			finder=finder->next;
			
		}
		for(int j=0;j<n;j++)	//sprawdzenie przynależno?i wierzchołków do biura
		{
			if(pomoc[j]!=1)
			{    
				matryca[j]=false;	//wierzchołek j należy do tego biura
           		}
            		else
            		{
                		pomoc[j]=0;
            		}
          	}
          	delete [] pomoc;
		
	}
	int *wynik=new int[n];
	for(int i=0;i<n;i++)
		wynik[i]=0;
	
	for(int i=0;i<n;i++)	 //obliczenie ile osób należy do biura numer 0 
                             //(przypominam że w tablicach numerujemy od zera =P)
		if(matryca[i]!=true)//do danego biura należš osoby które w tablicy 
                            //matryca sš zaznaczone jako FALSE
			wynik[0]++;
	int liczbaBiur=1;
	for(;;)				//wła?iwa pętla wykonujšca algorytm (dla pozostałych 
                        //wierzchołków)
	{
		int i=-1;
		for(int j=0;j<n;j++)	//wybranie wierzchołka nieprzydzielonego jeszcze
                                // do żadnego biura
			if(matryca[j]==true)
			{
				i=j;
				break;
			}
		if(i<0)
			break;		//je?i wszystkie zostały przydzielone to opuszczamy pętlę
		int *biuro=new int[n];			
		finder=tabela[i].glowa;			//	W	C
		while(finder!=NULL)			//	Y	O
		{					//	K
			biuro[finder->cel]=1;		//	O	D
			finder=finder->next;		//	N	L
		}					//	A	A
		for(int k=0;k<n;k++)			//	N
		{					//	I	1
			if(biuro[k]==1)			//	E	
				continue;		//		W
			finder=tabela[k].glowa;		//	T	I
			int *pomoc=new int[n];		//	E	E
			while(finder!=NULL)		//	J	R
			{				//		Z
				pomoc[finder->cel]=1;	//	S	C
				finder=finder->next;	//	A	H
			}				//	M	O
			for(int j=0;j<n;j++)		//	E	Ł
			{				//	J	K
				if(pomoc[j]!=1)		//		A
					biuro[j]=0;	//	P
				else			//	R
				    pomoc[j]=0;		//	A
        		}				//	C
			delete [] pomoc;		//	Y
		}					//
		for(int i=0;i<n;i++)			//obliczenie ile osób należy do danego biura
			if(biuro[i]!=1)
				wynik[liczbaBiur]++;
		liczbaBiur++;
		for(int i=0;i<n;i++)			//przepisanie składu danego biura na matrycę
			if(biuro[i]!=1)
				matryca[i]=false;
			else
			    biuro[i]=0;
		delete [] biuro;
	}
	printf("%d\n", liczbaBiur);
	if(liczbaBiur==1)		//je?i mieli?y tylko jedno biuro to wy?ietlamy n
		printf("%d", n);
	else				//w przeciwnym wypadku sortujemy wyniki...
	{
		for(int j=liczbaBiur-1; j>0;j--)
		{
			    for(int i=0;i<j;i++)
			  {
						if(wynik[i]>wynik[i+1])
						{
							int temp=wynik[i];
							wynik[i]=wynik[i+1];
							wynik[i+1]=temp;
						}        
				}       
		 }
		for(int i=0;i<liczbaBiur;i++)	//...i je wy?ietlamy =)
			printf("%d ", wynik[i]);
	}
	delete [] wynik;			//zwalniamy zajętš pamięć...
	delete [] matryca;
	delete [] tabela;
	return 0;				//...i na tym kończy się cały algorytm =D
//KONIEC
}    
Pobierz plik tekstowy
Administrator WJL
PHP&SQL coded by NOVA-IT