Tävlingsprogrammering/Uppgifter/Gruppindelning
Gruppindelning (PO-onlinekvalet 2008)
Under en skolutflykt ska eleverna delas in i olika grupper. Naturligtvis vill eleverna vara i samma grupp som sina kompisar. Skriv ett program som, givet namnet på varje elev samt vem som är kompis med vem, beräknar det maximala antalet grupper som eleverna kan delas in i (om eleverna får som de vill).
Indata
På första raden står ett heltal: antalet elever som ska på utflykt (2 ≤ n ≤ 100). Därefter följer n rader, var och en innehållande namnet på en elev. Varje namn är mellan 1 och 20 tecken långt och innehåller endast bokstäverna A-Z. Alla elever har olika namn. Sedan följer en rad med ett heltal: antalet kompispar (1 ≤ m ≤ 5050). Slutligen följer m rader innehållande kompisparen. För varje par anges två namn på samma rad, separerade med ett mellanslag.
Utdata
Programmet ska skriva ut en rad med ett heltal: det maximala antalet grupper som eleverna kan delas in i.
Exempel: Indata
6 KALLE MAJA SARA SVEN HUGO ANNA 3 KALLE ANNA MAJA ANNA SARA HUGO
Exempel: Utdata
3
Lösning[redigera]
Denna uppgift kan betraktas som ett grafproblem, där varje elev är en nod och varje kompispar en båge i grafen. Eftersom två barn som känner varandra måste tillhöra samma grupp, innebär det att alla elever som känner varandra direkt eller indirekt måste tillhöra samma grupp. Så två elever (kalla dem X och Y) kan endast tillhöra olika grupper om det inte finns någon väg i grafen från X till Y.
Vi börjar med att "mappa" varje elev till ett tal mellan 0 och n-1. Därefter skapar vi en 2-dimensional array (matris) för att lagra kompisparen, där värdet i cell (x,y) förtäljer om x är kompis med y. Notera att matrisen är symmetrisk eftersom kompisrelationen är kommutativ. Sist bygger vi upp grupperna. Detta kan göras med en DFS-sökning (rekursion), men i lösningen nedan har jag valt att istället använda Floyd-Warshalls algoritm. Det är inte den effektivaste implementation för det här problemet (sett till körtid), men den är enklast att koda och tillräckligt snabb eftersom antalet elever var väldigt begränsat.
Lösningsexempel i C#:
using System.Collections.Generic;
using System.IO;
public class Uppgift3
{
public static void Main(string[] args)
{
Solve(new StreamReader("gruppindelning1.in"), Console.Out);
}
public static void Solve(TextReader tr, TextWriter tw)
{
int n = int.Parse(tr.ReadLine());
Dictionary<string, int> nameMap = new Dictionary<string, int>();
for (int i = 0; i < n; i++)
nameMap.Add(tr.ReadLine(), nameMap.Count);
bool[,] conn = new bool[n,n];
for (int i = 0; i < n; i++)
conn[i, i] = true;
int m = int.Parse(tr.ReadLine());
for (int i = 0; i < m; i++)
{
string[] friends = tr.ReadLine().Split(' ');
int x = nameMap[friends[0]];
int y = nameMap[friends[1]];
conn[x, y] = conn[y, x] = true;
}
// Floyd-Warshall
for (int k = 0; k < n; k++)
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
conn[i, j] |= conn[i, k] && conn[k, j];
int groups = 0;
bool[] taken = new bool[n];
for (int i = 0; i < n; i++)
{
if (taken[i])
continue;
groups++;
taken[i] = true;
for (int j = 0; j < n; j++)
if (conn[i, j])
taken[j] = true;
}
tw.WriteLine(groups);
}
}
Ett lösningsexempel i Java som använder sig av standardklassen HashSet. Vi sparar kompisparen i grupper och om någon av kompisarna vi läser in redan finns i någon grupp, så lägger vi till båda kompisarna i den gruppen, annars bildar kompisparet en ny grupp. Slutligen räknas också alla elever som inte har några kompisar till antalet grupper.
import java.util.*;
import java.io.*;
public class Gruppindelning
{
//Använder man BufferedReader måste man kasta IOException,
// såvida man inte vill fånga det, vilket inte vi orkar.
public static void main(String [] klein) throws IOException
{
Scanner scan = new Scanner(System.in);
//Krävs för inläsning av rader med mellanslag.
BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
//Våra grupper.
ArrayList <HashSet<String>> grupp = new ArrayList <HashSet<String>> ();
System.out.print("Antal elever: ");
int antal = scan.nextInt();
//Våra elever.
String [] elever = new String [antal];
//Läser in eleverna.
for(int i = 0; i<antal; i++)
{
System.out.print("Elev " + (i+1) + ": ");
elever[i] = scan.next();
}
System.out.print("Antal par kompisar: ");
int friends = scan.nextInt();
//Läser in alla kompispar och lägger till dem i grupper samtidigt.
for(int i = 0; i<friends; i++)
{
//Om någon i paret redan fanns i en grupp.
boolean exists = false;
//Läser in kompisparet och sedan särar på namnen.
System.out.print("Par " + (i+1) + ": ");
String [] pair = in.readLine().split(" ");
//Går igenom alla grupper.
for(int j = 0; j<grupp.size(); j++)
{
//Gruppen vi för tillfället kollar på.
HashSet <String> current = grupp.get(j);
//Om någon i kompisparet finns i gruppen, så läggs båda
// till i den gruppen.
if(current.contains(pair[0]) || current.contains(pair[1]))
{
current.add(pair[0]);
current.add(pair[1]);
exists = true;
break; //Avbryter.
}
}
//Om kompisparet inte återfanns i någon grupp, så får de bilda en egen ny grupp.
if(!exists)
{
//Skapar gruppen.
HashSet <String> newGroup = new HashSet <String> ();
//Lägger till eleverna i gruppen.
newGroup.add(pair[0]);
newGroup.add(pair[1]);
//Sparar gruppen.
grupp.add(newGroup);
}
}
//Hur många grupper vi har.
int max = grupp.size();
//Dock kan det finnas elever som inte har några kompisar.
//De får då bilda en egen grupp för sig själv (får man tänka).
//Går igenom alla elever.
for(String s : elever)
{
//Finns eleven i någon grupp?
boolean exists = false;
//Går igenom alla grupper.
for(int i = 0; i<grupp.size(); i++)
{
//Nuvarande grupp vi kollar på.
HashSet <String> current = grupp.get(i);
//Om eleven finns i gruppen så kan vi avbryta.
if(current.contains(s))
{
exists = true;
break;
}
}
//Om eleven inte återfanns i någon grupp så får vi tänka att
// den skapar en egen grupp och således ökar antalet med 1.
if(!exists) max++;
}
//Skriver ut svaret.
System.out.println("Max antal grupper: " + max);
}
}