k-edge connected componentsTime Limit: 4000/2000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 227 Accepted Submission(s): 155
Efficiently computing k-edge connected components in a large graph G = (V, E), where V is the vertex set and E is the edge set, is a long standing research problem. It is not only fundamental in graph analysis but also crucial in graph search optimization algorithms. Computing k-edge connected components has many real applications. For example, in social networks, computing k-edge connected components can identify the closely related entities to provide useful information for social behavior mining. In a web-link based graph, a highly connected graph may be a group of web pages with a high commonality, which is useful for identifying the similarities among web pages. In computational biology, a highly connected subgraph is likely to be a functional cluster of genes for biologist to conduct the study of gene microarrays. Computing k-edge connected components also potentially contributes to many other technology developments such as graph visualization, robust detection of communication networks, community detection in a social network.
Clearly, if a graph G is not k-edge connected, there must be a set C of edges, namely a cut, such that the number |C| of edges in C is smaller than k and the removal of the edges in C cuts the graph G into two disconnected subgraphs G1 and G2. A connected component is a maximal connected subgraph of G. Note that each vertex belongs to exactly one connected component, as does each edge.
Now, we give you a undirected graph G with n vertices and m edges without self-loop or multiple edge, your task is just find out the number of k-edge connected components in G.
Multicases. 3 integer numbers n, m and k are described in the first line of the testcase.(3¡Ün¡Ü100, 1¡Üm¡Ün¡Á(n-1)/2,2¡Ük¡Ün)The following m lines each line has 2 numbers u, v describe the edges of graph G.(1¡Üu,v¡Ün,u¡Ùv)
A single line containing the answer to the problem.