Gathering of the GreatProblem code: KC202 |
All submissions for this problem are available.
Points:10
Evading the agents of the church was of prime importance for the Brotherhood of Brom, for if caught they would hanged, or burnt at the stake, or worse... Instead of having just a single meeting place they had multiple spots so that if one location was somehow compromised, they could use the other. Hence they needed to chose their meeting spots very carefully in the city. They chose them in such a manner that each meeting place was always connected to all the other alternate meeting spots.
Last night as you were going through the junk in your attic, you came across an ancient manuscript. Turns out that it is actually a map drawn by your greatest grandfather himself of the whole city as it was at that time. You could probably track down their meeting locations by finding sets of spots on the map that were always completely interconnected. It would be easier to visualise the map as a graph with the roads as the edges and the possible meeting locations as the nodes.
Consider a graph G formed from a large number of nodes connected by edges.
G is said to be connected if a path can be found in 0 or more steps between any pair of nodes in G. For example, the graph below is not connected because there is no path from A to C.
This graph contains, however, a number of subgraphs that are connected, one for each of the following sets of nodes: {A}, {B}, {C}, {D}, {E},
{A,B}, {B,D}, {C,E}, {A,B,D}
A connected subgraph is maximal if there are no nodes and edges in the original graph that could be added to the subgraph and still leave it connected. There are two maximal connected subgraphs above, one associated
with the nodes {A, B, D} and the other with the nodes {C, E}.
Write a program to find the number of maximal connected subsections(subgraphs) of the city(graph).
Input:
The first line contains the number of test cases T. T<=100 The first line of each input set contains a single uppercase alphabetic character. This character represents the largest node name in the graph. Each successive line contains a pair of uppercase alphabetic characters denoting an edge in the graph. Input is terminated by #.
Output:
For each test case, the output the number of maximal connected subgraphs.
Example:
Input:1 E AB CE DB ECOutput:
2
| Author: | ankitbabbar |
| Date Added: | 16-10-2009 |
| Time Limit: | 5 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
in the example given, '#' is
in the example given, '#' is not shown
does it come after EC in this case?
Yeah..There is a # at the end
Yeah..There is a # at the end of the each input...Missed in the sample inputs..
From the problem statement it
From the problem statement it looks like this graph is undirected. Why does the sample input have both EC and CE?
is the max nu,ber of nodes
is the max nu,ber of nodes 26?
@anshul: Well i think the
@anshul: Well i think the maximum number of characters are 26...:)
Is there a "#" after every
Is there a "#" after every test case , or it denotes the end of complete input file ?
There is a # after every test
There is a # after every test case.
Could you please provide a
Could you please provide a sample input(only input and not output) that has at least two test cases. I am constant getting runtime errors and think that the input format is different then what is given.
2EABBCCDEE#EABCEDBEC#
the graph is directed or
the graph is directed or undirected??
the graph is directed
the graph is directed
If the graph is directed then
If the graph is directed then the example in the question should return 1 instead of 2. This is because subgraph corresponding to{A,B,D} won't have a path from A to D and from B to either A orD hence not fulfilling the condition given in the question for a graph to be connected.This leaved us with the only connected graph corresponding to {C,E}.
Please clarify.
THE GRAPH IS
THE GRAPH IS UNDIRECTED...There has been a wrong comment before by one of my team member.....but there can be mirrored inputs as CE and EC are the same..
CAN A SINGLE VERTEX FORM A
CAN A SINGLE VERTEX FORM A MAXIMAL CONNECTED SUBGRAPH??
CAN some1 answer neel's
CAN some1 answer neel's question??? if it is entered as EE will it be counted as a subgraph??
YES, a single vertex can form
YES, a single vertex can form a maximal connected graph...and EE will be counted as a subgraph..
plz can you give some other
plz can you give some other test cases.
Can you please tell me the
Can you please tell me the output of the following input
1
B
BB
AB
AA
#
the output will be 1
the output will be 1