fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. vector<vector<int>>adj;
  4. vector<int>comp,compSize;
  5.  
  6. void dfs(int u ,int id){
  7.  
  8. 	comp[u]=id;
  9. 	compSize[id]++;
  10.  
  11. 	for(int v : adj[u]){
  12. 		if(comp[v] == -1)dfs(v,id);
  13. 	}
  14. }
  15. int spread(int n , vector<int>&from , vector<int>&to,vector<int>&mal){
  16. 	adj.assign(n+1,{});
  17. 	for(int i = 0 ; i < from.size();i++){
  18. 		adj[from[i]].push_back(to[i]);
  19. 		adj[to[i]].push_back(from[i]);
  20. 	}
  21.  
  22. 	 comp.assign(n + 1, -1);
  23.         compSize.assign(n + 1, 0);
  24.         	int id = 0;
  25. 	for(int i = 1 ; i <=n;i++){
  26. 		if(comp[i]==-1){
  27. 			dfs(i,id);
  28. 			id++;
  29. 		}
  30. 	}
  31.  
  32. 	vector<int>inf(id,0);
  33. 	for(int i = 1; i<=n;i++){
  34. 		if(mal[i]== 1)inf[comp[i]]++;
  35. 	}
  36. 	int ans = -1;
  37. 	int maxS = -1;
  38. 	for(int i = 0;i <= n ;i++){
  39. 		if(mal[i]==0)continue;
  40.  
  41. 		int c =  comp[i];
  42.  
  43. 		if(inf[c] == 1){
  44. 			if(comp[c] > maxS ){
  45. 				maxS = comp[c];
  46. 				ans = i;
  47. 			}else if(comp[c] == maxS && i < ans){
  48. 				ans = i;
  49. 			}
  50. 		}
  51. 	if(ans == -1){
  52. 		for(int i = 1;i<=n;i++){
  53. 			if(mal[i]==1)return i;
  54. 		}
  55. 	}
  56. 	}
  57.  
  58.  
  59. 	return ans;
  60. }
  61. int main() {
  62. 	int n ,m;
  63. 	cin>>n>>m;
  64. 	vector<int>from(m),to(m);
  65.  
  66. 	for(int i = 0 ;i < m ;i++){
  67. 		cin>>from[i];
  68. 	}
  69.  
  70. 	for(int i = 0;i < m ;i++){
  71. 		cin>>to[i];
  72. 	}
  73.  
  74. 	vector<int>mal(n+1);
  75.  
  76. 	for(int i= 1;i<=n;i++){
  77. 		cin>>mal[i];
  78. 	}
  79. 	cout<<spread(n,from,to,mal);
  80. }
Success #stdin #stdout 0s 5320KB
comments (?)
stdin
copy 
9 5
1 2 4 6 7
2 3 5 7 8
0 0 1 0 1  0 0 0 0
stdout
copy 
3
https://ideone.com/DQtB3R
language:
C++ (gcc 8.3)
created:
3 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!