fork download
copy 
  1. import java.io.*;
  2. import java.math.BigDecimal;
  3. import java.math.BigInteger;
  4. import java.util.*;
  5.  
  6.  
  7.  
  8.  
  9. public class Main {
  10. 	static class Reader 
  11.     { 
  12.         final private int BUFFER_SIZE = 1 << 16; 
  13.         private DataInputStream din; 
  14.         private byte[] buffer; 
  15.         private int bufferPointer, bytesRead; 
  16.  
  17.         public Reader() 
  18.         { 
  19.             din = new DataInputStream(System.in); 
  20.             buffer = new byte[BUFFER_SIZE]; 
  21.             bufferPointer = bytesRead = 0; 
  22.         } 
  23.  
  24.         public Reader(String file_name) throws IOException 
  25.         { 
  26.             din = new DataInputStream(new FileInputStream(file_name)); 
  27.             buffer = new byte[BUFFER_SIZE]; 
  28.             bufferPointer = bytesRead = 0; 
  29.         } 
  30.  
  31.         public String readLine() throws IOException 
  32.         { 
  33.             byte[] buf = new byte[64]; // line length 
  34.             int cnt = 0, c; 
  35.             while ((c = read()) != -1) 
  36.             { 
  37.                 if (c == '\n') 
  38.                     break; 
  39.                 buf[cnt++] = (byte) c; 
  40.             } 
  41.             return new String(buf, 0, cnt); 
  42.         } 
  43.  
  44.         public int nextInt() throws IOException 
  45.         { 
  46.             int ret = 0; 
  47.             byte c = read(); 
  48.             while (c <= ' ') 
  49.                 c = read(); 
  50.             boolean neg = (c == '-'); 
  51.             if (neg) 
  52.                 c = read(); 
  53.             do
  54.             { 
  55.                 ret = ret * 10 + c - '0'; 
  56.             }  while ((c = read()) >= '0' && c <= '9'); 
  57.  
  58.             if (neg) 
  59.                 return -ret; 
  60.             return ret; 
  61.         } 
  62.  
  63.         public long nextLong() throws IOException 
  64.         { 
  65.             long ret = 0; 
  66.             byte c = read(); 
  67.             while (c <= ' ') 
  68.                 c = read(); 
  69.             boolean neg = (c == '-'); 
  70.             if (neg) 
  71.                 c = read(); 
  72.             do { 
  73.                 ret = ret * 10 + c - '0'; 
  74.             } 
  75.             while ((c = read()) >= '0' && c <= '9'); 
  76.             if (neg) 
  77.                 return -ret; 
  78.             return ret; 
  79.         } 
  80.  
  81.         public double nextDouble() throws IOException 
  82.         { 
  83.             double ret = 0, div = 1; 
  84.             byte c = read(); 
  85.             while (c <= ' ') 
  86.                 c = read(); 
  87.             boolean neg = (c == '-'); 
  88.             if (neg) 
  89.                 c = read(); 
  90.  
  91.             do { 
  92.                 ret = ret * 10 + c - '0'; 
  93.             } 
  94.             while ((c = read()) >= '0' && c <= '9'); 
  95.  
  96.             if (c == '.') 
  97.             { 
  98.                 while ((c = read()) >= '0' && c <= '9') 
  99.                 { 
  100.                     ret += (c - '0') / (div *= 10); 
  101.                 } 
  102.             } 
  103.  
  104.             if (neg) 
  105.                 return -ret; 
  106.             return ret; 
  107.         } 
  108.  
  109.         private void fillBuffer() throws IOException 
  110.         { 
  111.             bytesRead = din.read(buffer, bufferPointer = 0, BUFFER_SIZE); 
  112.             if (bytesRead == -1) 
  113.                 buffer[0] = -1; 
  114.         } 
  115.  
  116.         private byte read() throws IOException 
  117.         { 
  118.             if (bufferPointer == bytesRead) 
  119.                 fillBuffer(); 
  120.             return buffer[bufferPointer++]; 
  121.         } 
  122.  
  123.         public void close() throws IOException 
  124.         { 
  125.             if (din == null) 
  126.                 return; 
  127.             din.close(); 
  128.         } 
  129.     }
  130.  
  131. 	public static PrintWriter out = new PrintWriter (new BufferedOutputStream(System.out));
  132. 	public static Reader sc = new Reader();
  133.  
  134. 	static int mod = (int)(1e9+7),MAX=(int)(2e6+10);
  135. 	static List<Integer>[] edges;
  136.  
  137. 	public static void main(String[] args) throws IOException{
  138.  
  139. 		  int n = sc.nextInt();
  140. 	        int m = sc.nextInt();
  141.  
  142. 	        edges = new ArrayList[n + 1];
  143. 	        for (int i = 0; i < edges.length; ++i) edges[i] = new ArrayList<>();
  144.  
  145. 	        for (int i = 0; i < m; ++i) {
  146. 	            int u = sc.nextInt();
  147. 	            int v = sc.nextInt();
  148. 	            edges[u].add(v);
  149. 	            edges[v].add(u);
  150. 	        }
  151.  
  152.  
  153. 	        int[] col = new int[n + 1];
  154. 	        Arrays.fill(col, -1);
  155.  
  156. 	        boolean is_bipartite = true;
  157. 	        Queue<Integer> q = new ArrayDeque<>();
  158. 	        for (int st = 1; st <= n && is_bipartite; ++st) {
  159. 	            if (col[st] == -1) {
  160. 	                q.add(st);
  161. 	                col[st] = 0;
  162. 	                while (q.size() > 0) {
  163. 	                    int v = q.poll();
  164. 	                    for (int node : edges[v]) {
  165. 	                        if (col[node] == -1) {
  166. 	                            col[node] = col[v] ^ 1;
  167. 	                            q.add(node);
  168. 	                        } else {
  169. 	                            is_bipartite &= col[node] != col[v];
  170. 	                        }
  171. 	                    }
  172. 	                }
  173. 	            }
  174. 	        }
  175.  
  176. 	        if (is_bipartite) {
  177. 	            for (int i = 1; i <= n; ++i) out.print((col[i] + 1) + " ");
  178. 	        } else out.println("IMPOSSIBLE");
  179. 	        out.close();
  180. 	    }
  181.  
  182. }
Success #stdin #stdout 0.09s 34100KB
comments (?)
stdin
copy 
5 3
1 2
1 3
4 5
stdout
copy 
1 2 2 1 2
https://ideone.com/K32kmB
language:
Java (HotSpot 12)
created:
3 years ago
visibility:
public

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!