fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define pb push_back
  3. #define pii pair<int,int>
  4. #define fi first
  5. #define int long long
  6. #define se second
  7. #define ios ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
  8. #define TXT "color3"
  9. #define endl cout<<"\n";
  10. #define freo if(fopen(TXT".inp","r")){freopen(TXT".inp","r",stdin); freopen(TXT".out","w",stdout);}             ///TEMPLATE MADE BY NIETTRAAN
  11. using namespace std;
  12.  
  13. const int MXN = 1005;
  14. vector<int> adj[MXN];
  15. string orig, res;
  16. int n, m;
  17. bool vis[MXN];
  18.  
  19. vector<int> comp;
  20.  
  21. bool bfs_component(int start) {
  22.     comp.clear();
  23.     queue<int> q;
  24.     q.push(start);
  25.     vis[start] = 1;
  26.     comp.pb(start);
  27.     while(!q.empty()) {
  28.         int u = q.front(); q.pop();
  29.         for(int v : adj[u]) {
  30.             if(!vis[v]) {
  31.                 vis[v] = 1;
  32.                 q.push(v);
  33.                 comp.pb(v);
  34.             }
  35.         }
  36.     }
  37.  
  38.     // thử 3 màu gốc
  39.     for(char startColor : {'R','G','B'}) {
  40.         if (startColor == orig[start]) continue; // phải khác màu cũ
  41.         map<int,char> color;
  42.         queue<int> qq;
  43.         qq.push(start);
  44.         color[start] = startColor;
  45.  
  46.         bool ok = true;
  47.         while(!qq.empty() && ok) {
  48.             int u = qq.front(); qq.pop();
  49.             for(int v : adj[u]) {
  50.                 if(color.count(v)) {
  51.                     if(color[v] == color[u]) {ok=false; break;}
  52.                 } else {
  53.                     // tìm màu cho v khác color[u] và khác orig[v]
  54.                     bool found = false;
  55.                     for(char c : {'R','G','B'}) {
  56.                         if(c != color[u] && c != orig[v]) {
  57.                             color[v] = c;
  58.                             found = true;
  59.                             break;
  60.                         }
  61.                     }
  62.                     if(!found){ok=false; break;}
  63.                     qq.push(v);
  64.                 }
  65.             }
  66.         }
  67.  
  68.         if(ok) {
  69.             for(auto &x : color) res[x.fi] = x.se;
  70.             return true;
  71.         }
  72.     }
  73.     return false;
  74. }
  75.  
  76. void solve() {
  77.     cin >> n >> m;
  78.     cin >> orig;
  79.     orig = " " + orig;
  80.     res.resize(n+1,' ');
  81.     for(int i=1;i<=m;i++){
  82.         int u,v;cin>>u>>v;
  83.         adj[u].pb(v);
  84.         adj[v].pb(u);
  85.     }
  86.  
  87.     for(int i=1;i<=n;i++){
  88.         if(!vis[i]){
  89.             if(!bfs_component(i)){
  90.                 cout << "Impossible\n";
  91.                 return;
  92.             }
  93.         }
  94.     }
  95.  
  96.     for(int i=1;i<=n;i++) cout << res[i];
  97.     cout << "\n";
  98. }
  99.  
  100. int32_t main(){
  101.     ios;
  102.     freo;
  103.     solve();
  104.     return 0;
  105. }
  106.  
Success #stdin #stdout 0s 5332KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/YoQgHT
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
11 days 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!