1. Martin Lambeck

package acm_334_identifying_concurrent_events;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Scanner;

/**
* FWP, Ausgew¦hlte Probleme aus dem ACM Programming Contest, SS10
* Problem: acm_334_identifying_concurrent_events
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=5&page=show_problem&problem=270
*
* @author Martin Lambeck
* @version 1.0, 14.08.2010
*
* Method : directed graph, independent nodes
* Status : PE
* Runtime: 0.136
*/


public class Main
{
static Scanner sc = new Scanner(System.in);
static int tcase = 0;

public static void main(String... args)
{
while (testcase())
;
}

public static boolean testcase()
{
int len = sc.nextInt();

if (len == 0)
return false;

Event.nextid = 0;

HashMap<String, Event> events;
Event[] evid;
int[][] adja;

ArrayList<LinkedList<Event>> lle = new ArrayList<LinkedList<Event>>(len);

for (int i = 0; i < len; i++)
{
int evs = sc.nextInt();

LinkedList<Event> ll = new LinkedList<Event>();

lle.add(ll);

for (int j = 0; j < evs; j++)
ll.add(new Event(sc.next().trim()));
}


evid = new Event[Event.nextid];
events = new HashMap<String, Event>(evid.length);
adja = new int[evid.length][evid.length];

for (LinkedList<Event> le : lle)
{
Event before = null;

for (Event e : le)
{
evid[e.id] = e;
events.put(e.name, e);

if (before != null)
{
before.out.add(e);
adja[before.id][e.id] = 1;
}

before = e;
}
}


len = sc.nextInt();

for (int i = 0; i < len; i++)
{
Event send = events.get(sc.next().trim());
Event recv = events.get(sc.next().trim());

send.out.add(recv);

adja[send.id][recv.id] = 1;
}



for (Event e : events.values())
{
bfs(adja[e.id], e);
}

ArrayList<String> print = new ArrayList<String>(2);
int conc = 0;

for (int i = 0; i < evid.length; i++)
{
for (int j = i+1; j < evid.length; j++)
{
if (adja[i][j] + adja[j][i] == 0)
{
conc++;
if (print.size() < 2)
{
print.add("(" + evid[i].name + "," + evid[j].name + ")");
}
}
}
}

tcase++;

if (conc > 0)
{
System.out.printf("Case %d, %d concurrent events: %n", tcase, conc);

System.out.println(print.get(0) + (conc >= 2 ? " " + print.get(1) + " " : ""));

} else
{
System.out.printf("Case %d, no concurrent events.%n", tcase);
}


return true;
}

static void bfs (int[] adja, Event start)
{
LinkedList<Event> q = new LinkedList<Event>();

q.add(start);

while (q.size() > 0)
{
Event e = q.pollFirst();

for (Event out : e.out)
{
adja[out.id] = 1;
q.add(out);
}
}
}
}

class Event
{
static int nextid = 0;

String name;
int id;
LinkedList<Event> out = new LinkedList<Event>();

public Event(String n)
{
name = n;
id = nextid++;
}
}