fork download
copy 
  1. import java.io.*;
  2. import java.util.*;
  3.  
  4. public class Solution implements Runnable {
  5.  
  6. 	class DSU{
  7. 		int[] arr;
  8. 		DSU(int n) {
  9. 			arr = new int[n];
  10. 			for(int i=0;i<n;++i)
  11. 				arr[i]=i;
  12. 		}
  13.  
  14. 		int get(int v){
  15. 			if(arr[v]==v)
  16. 				return v;
  17. 			return arr[v]=get(arr[v]);
  18. 		}
  19.  
  20. 		void union(int a,int b){
  21. 			arr[get(a)]=get(b);
  22. 		}
  23. 	}
  24.  
  25. 	class Edge{
  26. 		int a,b;
  27.  
  28. 		Edge(int a, int b) {
  29. 			this.a = a;
  30. 			this.b = b;
  31. 		}
  32. 	}
  33.  
  34. 	void solve() throws IOException {
  35. 		int n=nextInt(),m=nextInt();
  36. 		Edge[] edges = new Edge[m];
  37. 		int[] deg = new int[n];
  38. 		boolean[] is_useful = new boolean[n];
  39. 		for(int i=0;i<m;++i){
  40. 			edges[i] = new Edge(nextInt()-1,nextInt()-1);
  41. 			++deg[edges[i].a];
  42. 			++deg[edges[i].b];
  43. 		}
  44.  
  45. 		int minIndex = 0;
  46. 		for(int i=0;i<n;++i){
  47. 			if(deg[i]<deg[minIndex]){
  48. 				minIndex = i;
  49. 			}
  50. 		}
  51.  
  52.  
  53. 		ArrayList<Integer> useful = new ArrayList<Integer>();
  54. 		useful.add(minIndex);
  55.  
  56. 		for(Edge edge : edges){
  57. 			if(edge.b == minIndex){
  58. 				int tmp = edge.a;
  59. 				edge.a=edge.b;
  60. 				edge.b=tmp;
  61. 			}
  62.  
  63. 			if(edge.a == minIndex){
  64. 				is_useful[edge.b] = true;
  65. 				useful.add(edge.b);
  66. 			}
  67. 		}
  68.  
  69. 		Collections.sort(useful);
  70. 		HashMap<Integer, Integer> ht = new HashMap<Integer, Integer>();
  71. 		for(int i=0;i<useful.size();++i)
  72. 			ht.put(useful.get(i),i);
  73. 		int[] toUnUse = new int[useful.size()];
  74. 		boolean [][] graph = new boolean[useful.size()][useful.size()];
  75.  
  76. 		for(Edge edge : edges){
  77. 			if(is_useful[edge.a] && is_useful[edge.b]){
  78. 				graph[ht.get(edge.a)][ht.get(edge.b)] = true;
  79. 			}
  80. 			else if(is_useful[edge.a]){
  81. 				++toUnUse[ht.get(edge.a)];
  82. 			}
  83. 			else if(is_useful[edge.b]){
  84. 				++toUnUse[ht.get(edge.b)];
  85. 			}
  86. 		}
  87.  
  88. 		for(int i=0;i<useful.size();++i){
  89. 			if(toUnUse[i] == n-useful.size() + 1){
  90. 				graph[i][ht.get(minIndex)] = true;
  91. 			}
  92. 		}
  93.  
  94. 		DSU dsu = new DSU(n);
  95.  
  96. 		for(int i=0;i<useful.size();++i)
  97. 			for(int j=0;j<useful.size();++j)
  98. 				if(!graph[i][j] && !graph[j][i])
  99. 					dsu.union(i,j);
  100.  
  101. 		ArrayList<Integer>[] anses = new ArrayList[useful.size()];
  102. 		for(int i=0;i<useful.size();++i){
  103. 			anses[i] = new ArrayList<Integer>();
  104. 		}
  105.  
  106. 		for(int i=0;i<n;++i){
  107. 			anses[dsu.get(ht.get(is_useful[i]?i : minIndex))].add(i);
  108. 		}
  109.  
  110. 		int empty = 0;
  111.  
  112. 		for(int i=0;i<useful.size();++i)
  113. 			if(anses[i].isEmpty())
  114. 				++empty;
  115.  
  116. 		out.println(useful.size() - empty);
  117.  
  118. 		for(int i=0;i<useful.size();++i){
  119. 			if(!anses[i].isEmpty()){
  120. 				out.print(anses[i].size());
  121. 				for(Integer j: anses[i]){
  122. 					out.print(" "+(j+1));
  123. 				}
  124. 				out.println();
  125. 			}
  126. 		}
  127. 	}
  128.  
  129. 	public static void main(String[] args) {
  130. 		new Solution().run();
  131. 	}
  132.  
  133. 	PrintWriter out;
  134. 	StringTokenizer st;
  135. 	BufferedReader br;
  136.  
  137. 	public void run() {
  138. 		out = new PrintWriter(System.out);
  139. 		br = new BufferedReader(new InputStreamReader(System.in));
  140. 		try {
  141. 			solve();
  142. 		} catch (IOException e) {
  143. 			out.println("IOException:");
  144. 			out.println(e.getStackTrace());
  145. 		}
  146. 		out.flush();
  147. 	}
  148.  
  149. 	public String nextString() throws IOException {
  150. 		while (st == null || !st.hasMoreTokens()) {
  151. 			st = new StringTokenizer(br.readLine());
  152. 		}
  153. 		return st.nextToken();
  154. 	}
  155.  
  156. 	public int nextInt() throws IOException {
  157. 		return Integer.parseInt(nextString());
  158. 	}
  159.  
  160. 	public double nextDouble() throws IOException {
  161. 		return Double.parseDouble(nextString());
  162. 	}
  163.  
  164. 	public long nextLong() throws IOException {
  165. 		return Long.parseLong(nextString());
  166. 	}
  167.  
  168.  
  169. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
Main.java:4: error: class Solution is public, should be declared in a file named Solution.java
public class Solution implements Runnable {
       ^
Note: Main.java uses unchecked or unsafe operations.
Note: Recompile with -Xlint:unchecked for details.
1 error
stdout
copy 
Standard output is empty
https://ideone.com/pxrBU6
language:
Java (12.0.1)
created:
9 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!