fork(3) download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define pb push_back
  4. #define mp make_pair
  5. int connectivity[500009] = {0};
  6. int parent[200001];
  7. bool visited[200001] = {0};
  8. vector < pair < int , int > > v[200001];
  9. vector < int > tree[200001];
  10. class compare
  11. {
  12. public:
  13. 	bool operator()(const pair < int  ,pair <int ,int > >  &n1 , const pair <int , pair <int , int > > &n2)
  14. 	{		
  15. 		return n1.second.second > n2.second.second;
  16. 	}
  17. };
  18. bool cmp(const pair <int, int> &n1 , const pair <int , int> &n2)
  19. {
  20. 	if(n1.first != n2.first)
  21. 		return n1.first < n2.first;
  22. 	else
  23. 		return n1.second > n2.second;
  24. }
  25. int calc(int x , vector <int> v[])
  26. {
  27. 	int i = 0;
  28. 	visited[x] = 1;
  29. 	for(i = 0;i < v[x].size();i++)
  30. 	{
  31. 		if(!visited[v[x][i]])
  32. 		{
  33. 			parent[v[x][i]] = x;
  34. 			connectivity[x] += calc(v[x][i] , v);
  35. 		}
  36. 	}
  37. 	if(parent[x] == 0)
  38. 		return connectivity[x];
  39. 	else
  40. 		return 1 + connectivity[x];
  41. }
  42. int main()
  43. {
  44. //	freopen("/home/bigdaddy/Documents/testgoogol03/3.in", "r", stdin);
  45. 	int n , m ,a ,j ,b, c ,i, cnt = 0 , strt;
  46. 	cin >> n >> m;
  47.  
  48.  
  49. 	for(i = 0;i < m;i++)
  50. 	{
  51. 		scanf("%d%d%d", &a, &b, &c);
  52. 	//	cin >> a >> b >> c;
  53. 		v[a].pb(mp(b, c));
  54. 		v[b].pb(mp(a, c));
  55. 	}
  56.  
  57. 	bool visited[500009] = {0};
  58. 	priority_queue <pair < int , pair <int ,long long int> > , vector <pair < int , pair <int ,long long int> > >,compare > q ;
  59. 	priority_queue <pair < int , int > > q2;
  60.  
  61. 	q.push(mp(0,mp(1,0)));
  62.  
  63. 	while(cnt < n)
  64. 	{
  65. 	//	cout << q.size() << endl;
  66. 		b = q.top().first;
  67. 		a = q.top().second.first;
  68. 		q.pop();
  69. 	//	cout << a << endl;
  70. 		if(!visited[a])
  71. 		{
  72. 			cnt++;
  73. 			visited[a] = 1;
  74. 			if(b > 0)
  75. 			{
  76. 				tree[b].pb(a);
  77. 				tree[a].pb(b);
  78. 			}
  79. 			for(i = 0;i < v[a].size() ; i++)
  80. 			{
  81. 				if(!visited[v[a][i].first])
  82. 				{
  83. 					q.push(mp(a ,v[a][i]));
  84. 				}
  85. 			}
  86. 		}
  87. 	}
  88. 	parent[1] = 0;
  89. 	int ans[n+1];
  90. 	calc(1 , tree);
  91.  
  92. 	for(i = 1;i <= n;i++)
  93. 	{
  94. 		ans[i] = 0;
  95. 		cnt = n-1;
  96. 		for(j = 0;j < tree[i].size() ;j++)
  97. 		{
  98. 			if(parent[tree[i][j]] == i)
  99. 			{
  100. 				cnt -= connectivity[tree[i][j]] + 1;
  101. 				ans[i] += cnt * (connectivity[tree[i][j]] + 1);
  102. 			}
  103. 		}
  104. 	}
  105. 	vector < pair <int , int> > v1;
  106. 	for(i = 1;i <= n;i++)
  107. 		v1.pb(mp(ans[i] , i));
  108.  
  109. 	sort(v1.begin() , v1.end() , cmp);
  110.  
  111. 	for(i = n-1 ; i >= 0 ; i--)
  112. 		cout << v1[i].second << endl;
  113.  
  114. 	return 0;
  115. }
Success #stdin #stdout 0s 11272KB
comments (?)
stdin
copy 
4 5
1 2 10 
2 3 15 
1 3 5 
4 2 2 
4 3 40
stdout
copy 
1
2
3
4
https://ideone.com/IJTq27
language:
C++ (gcc 8.3)
created:
8 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!