ADDED   SRM/378-U/1C.cpp
Index: SRM/378-U/1C.cpp
==================================================================
--- SRM/378-U/1C.cpp
+++ SRM/378-U/1C.cpp
@@ -0,0 +1,221 @@
+#include <iostream>
+#include <sstream>
+#include <iomanip>
+#include <vector>
+#include <string>
+#include <map>
+#include <set>
+#include <algorithm>
+#include <numeric>
+#include <iterator>
+#include <functional>
+#include <complex>
+#include <queue>
+#include <stack>
+#include <cmath>
+#include <cassert>
+#include <tuple>
+using namespace std;
+typedef long long LL;
+typedef complex<double> CMP;
+
+class TwistyPassages { public:
+	vector<int> similarRooms(vector<string> maze)
+	{
+		map<int,int> e2o;
+		Graph org = parse_graph(maze); // original graph
+		Graph exg = construct_extended_graph(org, &e2o); // extended graph
+		Groups groups = grouping(exg); // grouping
+
+		// similar[ov] = set of nodes indistinguishable from ov (in original graph)
+		vector<set<int>> similar(maze.size());
+		for(auto& e_grp: groups) {
+			set<int> o_grp;
+			for(int ev: e_grp)
+				o_grp.insert(e2o[ev]);
+			for(int ov: o_grp)
+				similar[ov].insert(o_grp.begin(), o_grp.end());
+		}
+
+		// similar[ov]-1 is the answer.
+		vector<int> answer(maze.size());
+		transform(similar.begin(), similar.end(), answer.begin(),
+			[](const set<int>& g){return g.size()-1;});
+		return answer;
+	}
+
+	typedef vector<vector<int>> Graph;
+	Graph parse_graph(const vector<string>& maze)
+	{
+		Graph g;
+		for(auto& m: maze) {
+			stringstream ss(m);
+			g.emplace_back(istream_iterator<int>(ss), istream_iterator<int>());
+		}
+		return g;
+	}
+
+	Graph construct_extended_graph(const Graph& org, map<int,int>* e2o)
+	{
+		map<pair<int,int>, int> o2e;
+		for(int v=0,id=0; v<org.size(); ++v) {
+			// special handling for outdeg = 0 node
+			if(org[v].size() == 0) {
+				(*e2o)[id] = v;
+				o2e[make_pair(v,0)] = id++;
+			}
+			for(int vi=0; vi<org[v].size(); ++vi) {
+				(*e2o)[id] = v;
+				o2e[make_pair(v,vi)] = id++;
+			}
+		}
+
+		Graph exg(o2e.size());
+		map<pair<int,int>, int> nodeid;
+		for(int v=0; v<org.size(); ++v)
+		for(int vi=0; vi<org[v].size(); ++vi) {
+			// (v,vi) : came to the room v from the vi-th road.
+			for(int k=0; k<org[v].size(); ++k) {
+				// Go k-th road clockwise from i-th. Reaches (u,ui).
+				int u = org[v][(vi+k) % org[v].size()];
+				int ui = find(org[u].begin(), org[u].end(), v) - org[u].begin();
+				// (v,vi)--k-->(u,ui)
+				exg[o2e[make_pair(v,vi)]].push_back(o2e[make_pair(u,ui)]);
+			}
+		}
+		return exg;
+	}
+
+	typedef set<set<int>> Groups;
+	Groups grouping(const Graph& G)
+	{
+		// "reverse_edge[u][e] has v" := v--e-->u
+		const int MaxEdgeNum = G.size();
+		vector<vector<vector<int>>> reverse_edge(G.size(), vector<vector<int>>(MaxEdgeNum));
+		for(int v=0; v<G.size(); ++v)
+			for(int e=0; e<G[v].size(); ++e)
+				reverse_edge[G[v][e]][e].push_back(v);
+
+		vector<int> group_id(G.size());
+		map<int, set<int>> groups;
+		int fresh_group_id = 0;
+		for(int v=0; v<G.size(); ++v) {
+			groups[G[v].size()].insert(v);
+			group_id[v] = G[v].size();
+			fresh_group_id = max(fresh_group_id, group_id[v]+1);
+		}
+
+		queue<set<int>> partitioner;
+		for(auto& kv: groups)
+			partitioner.push(kv.second);
+
+		while(!partitioner.empty())
+		{
+			set<int> P = partitioner.front();
+			partitioner.pop();
+
+			for(int e=0; e<MaxEdgeNum; ++e)
+			{
+				map<int, set<int>> g2u;
+				for(int v: P)
+					for(int u: reverse_edge[v][e])
+						g2u[group_id[u]].insert(u);
+				for(auto& kv: g2u) {
+					int gid = kv.first;
+					set<int>& enterP = kv.second;
+					if(groups[gid].size() != enterP.size()) {
+						for(int u: enterP) {
+							group_id[u] = fresh_group_id;
+							groups[gid].erase(u);
+						}
+						groups[fresh_group_id++] = enterP;
+						partitioner.push(enterP.size() < groups[gid].size() ? enterP : groups[gid]);
+					}
+				}
+			}
+		}
+
+		Groups result;
+		for(auto& kv: groups)
+			result.insert(kv.second);
+		return result;
+	}
+};
+
+// BEGIN CUT HERE
+#include <ctime>
+double start_time; string timer()
+ { ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
+template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
+ { os << "{ ";
+   for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
+   os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
+void verify_case(const vector <int>& Expected, const vector <int>& Received) {
+ bool ok = (Expected == Received);
+ if(ok) cerr << "PASSED" << timer() << endl;  else { cerr << "FAILED" << timer() << endl;
+ cerr << "\to: " << Expected << endl << "\tx: " << Received << endl; } }
+#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
+#define END	 verify_case(_, TwistyPassages().similarRooms(maze));}
+int main(){
+
+CASE(0)
+	string maze_[] = {"1 2 3", "0", "0", "0"};
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = {0, 2, 2, 2 };
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+CASE(1)
+	string maze_[] = {"1 2 3", "0", "0", "0 4", "3"};
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = {0, 0, 0, 0, 0 };
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+CASE(2)
+	string maze_[] = {"1 2 3", "0", "0", "0 4", "3",
+ "6 7 8", "5", "5", "5 9", "8"};
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = {1, 1, 1, 1, 1, 1, 1, 1, 1, 1 };
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+CASE(3)
+	string maze_[] = {"1 2 3 4",  "0", "0 5",  "0", "6 0",  "2", "4",
+"8 10 9 11", "7", "7 12", "7", "13 7", "9", "11"};
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = {0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0 };
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+CASE(4)
+	string maze_[] = {"1 2", "2 0", "0 1", "4 6", "5 3", "6 4", "3 5"};
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = {6, 6, 6, 6, 6, 6, 6 };
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+CASE(5)
+	string maze_[] = {"1 2 3", "4 5 0", "6 7 0", "8 9 0", "10 11 1", "12 13 1", 
+ "14 15 2", "16 17 2", "18 19 3", "20 21 3", "22 23 4", 
+ "24 25 4", "26 27 5", "28 29 5", "30 31 6", "32 33 6", 
+ "34 35 7", "36 37 7", "38 39 8", "40 41 8", "42 43 9", 
+ "44 45 9", "10", "10", "11", "11", "12", "12", "13", "13",
+ "14", "14", "15", "15", "16", "16", "17", "17", "18", "18",
+ "19", "19", "20", "20", "21", "21"};
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = {0, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 2 };
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+CASE(6)
+	string maze_[] = {"38 7 9 8 43 48 30 41 5 22 26 35 33 4", "14 39 25 35 30 45 18 12 10 8 21 46 22 37 20", "15 37 26 44 19 17 39 16 7 18 45 36 20 42 24", "21 43 26 8 28 10 4 48 25 46 49 31 37 27 15", "8 31 30 3 0 36 41 5 34 25 44 32 9 14 22", "46 33 38 4 47 34 17 6 45 10 41 48 31 43 0", "5 40 17 19 22 43 18 47 31 9 7 15 29 28 23", "19 38 21 11 34 31 9 0 48 30 44 2 26 16 6", "48 12 3 49 0 41 1 28 35 40 36 4 29 33 43", "18 36 6 47 26 37 27 22 0 46 23 41 4 24 7", "42 13 35 28 31 12 11 3 1 20 16 45 19 40 5", "14 15 45 46 13 7 27 39 25 38 44 17 16 10 43", "48 8 15 42 47 10 29 45 39 1 19 25 44 32 26", "47 24 11 36 41 42 16 38 37 20 32 31 45 29 10", "31 48 49 25 11 38 18 23 43 4 22 41 24 1 27", "32 34 23 11 6 43 2 22 48 45 17 41 12 16 3", "7 46 18 28 20 19 43 31 27 2 15 13 39 10 11", "19 26 28 2 30 23 15 5 24 47 25 18 6 42 11", "26 6 24 46 17 42 45 14 16 9 22 27 1 33 2", "30 6 17 37 39 33 49 2 21 46 16 27 7 10 12", "13 32 41 1 39 16 42 27 2 33 40 24 45 48 10", "36 37 41 1 30 7 23 35 40 44 26 47 39 3 19", "14 6 23 40 0 43 9 29 1 18 31 15 28 34 4", "30 14 6 28 34 22 48 9 40 21 42 17 15 37 32", "48 40 44 26 9 20 13 43 17 2 18 29 14 42 46", "32 12 43 1 17 39 29 14 3 36 11 40 4 49 33", "0 7 39 3 12 49 38 36 21 29 18 17 9 2 24", "29 28 38 16 18 46 9 3 35 36 40 20 14 11 19", "33 39 35 38 3 6 22 10 23 17 27 46 16 8 42", "13 26 25 37 33 44 12 48 6 41 46 24 8 22 27", "34 41 38 21 0 19 23 4 7 49 1 44 17 40 35", "3 14 32 4 5 37 7 6 13 10 22 16 44 47 49", "15 4 13 31 38 23 42 20 12 46 35 25 43 34 37", "39 44 19 0 18 28 20 37 29 48 8 45 25 5 34", "36 44 47 7 15 4 33 30 42 32 22 40 5 23 41", "40 27 42 8 45 32 10 0 28 1 49 46 30 47 21", "4 2 21 47 8 38 27 45 39 13 49 26 9 25 34", "42 21 31 29 13 47 32 3 9 33 2 23 45 1 19", "0 43 7 28 44 13 27 32 49 14 36 11 5 30 26", "16 36 21 20 12 48 26 41 2 11 28 33 1 19 25", "8 22 10 6 35 20 25 23 41 27 30 24 44 34 21", "13 29 39 15 0 30 40 20 4 5 34 14 8 9 21", "28 10 32 17 34 37 13 2 18 20 12 24 35 49 23", "5 47 25 24 11 8 14 38 16 6 32 15 22 3 0", "40 38 30 21 31 46 34 29 11 33 4 12 24 2 7", "35 49 36 10 12 11 37 18 33 2 20 1 13 15 5", "3 28 35 1 19 9 18 27 32 44 24 11 29 16 5", "9 43 6 31 12 13 35 21 36 5 49 34 48 17 37", "24 33 5 8 15 12 47 29 0 7 23 20 14 39 3", "19 3 14 8 38 47 30 36 35 25 31 26 42 45"};
+;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	  int __[] = {0};
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+/*
+CASE(7)
+	string maze_[] = ;
+	  vector <string> maze(maze_, maze_+sizeof(maze_)/sizeof(*maze_)); 
+	int __[] = ;
+	  vector <int> _(__, __+sizeof(__)/sizeof(*__)); 
+END
+*/
+}
+// END CUT HERE