当前没有测试数据。

1. 1.       Introduction
   Definition : An isomorphism from a simple graph G to a simple graph H is a bijection f:V(G) -> V(H) such that uv belongs to E(G) if and only if f(u)f(v) belongs to E(H) . We say “G is isomorphic to H”, if there is an isomorphism from G to H.
   Example : The following two graphs are isomorphic.

         G₁                                                                            G₂

Our objective in this problem is to find isomorphic graphs.

 

Input

 

Input is read from STDIN. Each test case consists of graphs all with same number of vertices. Your task in this assignment will be to divide the given set of graphs into classes within which graphs are pairwise isomorphic. 

k v [k is the number of graphs (<=20) in the test case and v is the number of vertices (<=20) in each of these graphs] 

e₁ [number of edges in first graph, call this graph ‘1’]

u₁ w₁

u₂ w₂

...

u_e1 w_e1

e₂ [number of edges in second graph, call this graph ‘2’]

u₁ w₁

u₂ w₂

...

u_e2 w_e2

e₃
...

...

...

e_k [number of edges in the last graph, call this graph ‘k’]

u₁ w₁

u₂ w₂

...

u_ek w_ek

[Note: all n graphs themselves are named ‘1’, ‘2’...’n’ in the order in which they appear in the input. Hence the graph with e₁ edges is called ‘1’ and so on]
[Note: all graphs are simple & undirected; vertices are labelled with numbers, not alphabets.]

Output

An isomorphic class is simply a list of graphs which belong to it. And Output is written to STDOUT.
The output should follow the below format:
1. Output is a listing of all isomorphic classes, one on each line, sorted in ascending order by the first
graph of the class.
2. Within an isomorphic class, the members are printed in ascending order.
(Thus, the class containing graph ‘1’ is always on line 1.)

Remarks

Problem statement is as described in the assignment pdf. Input output format is also descibed there.

More test cases will be added soon.

Do let us know if you find any errors/hit time limits/etc.

REMEMBER: This is an individual assignment.

		</p><div id="ccontent">
		<!-- google_ad_section_start -->

---

hide comments

<script language="JavaScript">
<!--
$(document).ready(function(){
    $('.pager_link').bind('click', function(me){
            var href=$(me.currentTarget).attr('href');
	$('#ccontent').animate({opacity: 0.5},1);
            $.ajax({
                    type: "GET",
                    url: href+",ajax=1",
                    contentType: "application/x-www-form-urlencoded;charset=ISO-8859-2",
                    success: function(data){
                            $('#ccontent').html(data);
			$('#ccontent').animate({opacity: 1.0},1);
                    },
                    error: function(err){
                            alert('error');
                    }
            });
            return false;
    });
});
-->
</script>




		
<tr>
	<td width="50" style="vertical-align:top;">
		<img src="file://yz3FNYUe.png">
	</td>
	<td class="comm comm_odd">
		<a href="/users/sourspinach">Jacob Plachta</a>: 
							<span style="font-size: 10px; color: #666;">2015-12-22 14:51:23</span>
	<br>
			<p>Something's wrong with the data - the values for u and w range between 0 and v, inclusive. I'm guessing that some graphs' nodes are 0-indexed while others are 1-indexed, or something.

However, I was able to get AC by incrementing v by 1, and then assuming that the nodes are 0-indexed (numbered 0 .. [original value of v]).</p> </td> </tr>

		<!-- google_ad_section_end -->
		</div>
		<table width="100%">
            <tbody><tr>
            <td colspan="2" height="20px"></td>
    </tr>
    <form method="post" action="/comment/EE4371/add/"></form>
    <tr> <td style="" colspan="2">Leave a Comment</td> </tr>
    <tr>
            <td valign="top"></td>
            <td><textarea name="content" rows="3" class="form-control"></textarea></td>
    </tr>
    <tr>
            <td colspan="2" style=""><br>
                    <input type="submit" value="Publish" class="btn btn-default">
                    <input type="hidden" name="pcode" value="EE4371">
            </td>
    </tr>

<tr> <td colspan="2">
Notes:
1. Don't post any source code here.
2. Please be careful, leave short comments only. Don't spam here.
3. For more discussion (hints, ideas, solutions) please visit our forum.
4. Authors of the problems are allowed to delete the post and use html code here (e.g. to provide some useful links). </td> </tr>

    </tbody></table>