Total Graphs (keteki)
All submissions for this problem are available.There is a connected graph with no loops and no cycles. You can disconnect a node from all the nodes it is connected to. Find the maximum number of connected components that can be formed by disconnecting one node in that graph, print that number.
Single input each test case.
5 test cases, each case 10 points.
The input starts with an integer N, the number of nodes in the graph. N lines follow, each having N integers seperated by spaces. The value at row i column j is 1 if there is a route between node i and node j.
Print the number, on a newline.
0 1 0
1 0 1
0 1 0
Explanation: If the second node(1 based index) of the graph is disconnected, then it would produce 3 new graphs containing 1 node each.
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, rust, SCALA, swift, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, kotlin, PERL6, TEXT, SCM chicken, PYP3, CLOJ, COB, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.