Given a connected undirected graph, find the minimum number of vertices beyond one that must hold servers so every vertex still reaches a server after any single edge is removed.
Hard8GraphDFSBrute forceImplementationNo attempts yetTime limit2sMemory limit512 MBA programming contest runs at several sites at the same time. The sites are joined by a network of two way links. Each link joins two different sites, and at most one link joins any pair of sites. Contestants submit their solutions to judging servers. A judging server sits at one site, and a contestant at some site can use that server when the two sites are still joined by working links.
Every contestant must have access to at least one judging server at all times. While every link works, the network joins all sites, so one judging server is enough. At the other extreme, a judging server at every site guarantees access even if every link fails. The organisers want to run as few judging servers as possible without losing that guarantee.
The network has one reliable property. At any moment exactly one link is broken, and a broken link carries nothing in either direction. Any link can be the broken one. The organisers want the smallest number of judging servers such that, whichever single link is broken, every site still reaches at least one judging server.
They already know that they must run at least one judging server. Report how many extra judging servers they must run beyond that first one.
The first line contains one integer S (2≤S≤100000), the number of sites. The sites are numbered 0 to S−1.
The next S lines describe the sites in order, starting with site 0. The line for site i starts with an integer ki (0≤ki<S), the number of links from site i to a site with a larger number. Then follow ki integers in ascending order, the sites those links go to. A link is two way, but it appears only on the line of its lower numbered site. The total number of links is at most 100000, and the links join all S sites into one network.
Print the minimum number of extra judging servers the organisers must run.