Tävlingsprogrammering/Uppgifter/Snailbook

Snailbook

Sociala nätverk är inget nytt. Redan på 1800-talet användes informella nätverk för att brevledes sprida nyheter och skvaller. Det kunde gå till så att varje deltagare hade en sändlista med personer hon skickade brev till när hon fick veta någon nyhet.

Tänk dig att du vill sprida en intressant nyhet till alla i detta nätverk (du är inte själv en del av det). Skriv ett program som, givet allas sändlistor, beräknar det minsta antalet personer du måste skicka nyheten till.

Indata

Första raden innehåller ett heltal 1 ≤ N ≤ 10000, antalet personer i nätverket. Personerna är numrerade från 1 till N. Därefter följer N rader som vardera beskriver sändlistan för en person (den första listan gäller person 1, den andra person 2 o.s.v.). Första talet på varje rad anger listans längd 0 ≤ K ≤ 100 och därefter följer K tal: numren på de personer som listans ägare skickar brev till.

Utdata

Ett heltal, det minsta antalet personer du måste skicka nyheten till för att den ska spridas till alla N personer.

Exempel: Indata

Exempel: Utdata

Exempel: Förklaring

Du kan exempelvis skicka nyheten till personerna 1, 5, 9 och 14.

Lösning

Detta är ett standardproblem i grafteori och kallas ibland för att hitta minimal dominator set. Eftersom få förväntas känna till den enkla lösningen (se t.ex. lösningen till ett gammalt IOI-problem , "The strategy for computing a minimal dominator set..." en bit ner på sidan), är det öppet för andra smarta lösningar.

Ett sätt att tänka är så här: Om det inte hade funnits några loopar i grafen, så hade det varit mycket enkelt. Skicka bara breven till de personer som inte får något brev (d.v.s. de noder som har ingrad 0), för alla andra får ju brev av någon och får därmed förr eller senare reda på nyheten.

Lyckligtvis finns det ett sätt att "ta bort" looparna så att den kvarvarande grafen är en s.k. DAG (directed acyclic graph). Mer generellt än bara enkla loopar, så letar man upp alla delmängder av noder (snailbook-grupper kanske...) som har den egenskapen att om man skickar ett brev till vem som helst i gruppen så når det alla andra. Dessa kallas strongly connected components och kan förstås också bestå av en ensam nod. En effektiv algoritm för att hitta dessa finns t.ex. beskriven på vår tränings-sajt. Därefter är det bara att räkna hur många av dessa grupper som inte får några brev "utifrån".

Lösning i C++

#include <stdio.h> 
#include <vector>
using namespace std;

vector<int> ed[10000], red[10000];
int sp, sorted[10000], vis[10000],co[10000];

void DFS1(int v) {
  int q;
  if(!vis[v]) {
    vis[v] = 1; //Markera noden som besökt
    for(q=0;q<ed[v].size();q++) DFS1(ed[v][q]);    //Loopa över nodens utbågar och rekursera
    sorted[--sp] = v;   //Sätt in noden i den sorterade listan över sluttider
  }
}

void DFS2(int v, int comp) {
  int q;
  if(!vis[v]) {
    vis[v] = 1;   //Markera noden som besökt
    co[v]=comp;   //Markera noden med komponentnumret
    for(q=0;q<red[v].size();q++) DFS2(red[v][q],comp);  //Loopa över nodens inbågar och rekursera
  }
}


int main() {
  int i,j,k,ned,a,b,q,numscc,source[10000],nv;
  scanf("%d", &nv);
  for(i=0;i<nv;i++) {
    scanf("%d", &ned);
    for(j=0;j<ned;j++) {
      scanf("%d", &k); 
      ed[i].push_back(k-1);    //Addera bågen i grafen
      red[k-1].push_back(i);   //Addera bågen i den omvända grafen
    }
  }
  numscc = 0;   //Räknare för strongly connected components (SCCs)
  sp = nv;      //index för att fylla i arrayen sorted baklänges
  for(a=0;a<nv;a++) vis[a] = 0;   //Markera alla noder som obesökta
  for(a=0;a<nv;a++) DFS1(a);      //Första DFS-rundan: samla sluttider för alla noder
  for(a=0;a<nv;a++) vis[a] = 0;   //Markera alla noder som obesökta igen
  for(a=0;a<nv;a++) if(!vis[sorted[a]]) { //Andra DFS-rundan: markera alla noder med deras SCC-nummer  
      DFS2(sorted[a],numscc);    
      numscc++;
    }
  for(a=0;a<numscc;a++) source[a] = 1;    //Markera alla SCCs som potentiella källor i komponentgrafen (ingrad 0)
  for(a=0;a<nv;a++) for(q=0;q<ed[a].size();q++) {   //Loopa över alla grafens bågar 
      b=ed[a][q];
      if(co[a]!=co[b]) source[co[b]]=0;  //Om bågen går mellan två olika SCCs så kan inte slutnoden vara en källa
    }
  q=0;
  for(a=0;a<numscc;a++) if(source[a]) q++;   //Räkna hur många källor som finns.
  printf("%d\n", q);
}