fork download
copy 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. using namespace std;
  7.  
  8. const int N=10005;
  9. int n,m;
  10. vector <int> G[N];
  11. vector <int> L;
  12. int Cnt[N];
  13. int label[N];
  14. int Q[N];
  15. int F[N];
  16.  
  17. int main(){
  18. 	scanf("%d%d",&n,&m);
  19. 	for (int i=1;i<=n;i++) G[i].clear();
  20. 	for (int i=0;i<m;i++){
  21. 		int x,y;
  22. 		scanf("%d%d",&x,&y);
  23. 		G[x].push_back(y);
  24. 		G[y].push_back(x);
  25. 	}
  26. 	for (int i=1;i<=n;i++) Cnt[i]=label[i]=0;
  27. 	for (int i=n;i>=1;i--){
  28. 		int Max=-1;
  29. 		int Maxi=-1;
  30. 		for (int j=1;j<=n;j++)
  31. 			if (label[j]==0 && Cnt[j]>Max){
  32. 				Max=Cnt[j];
  33. 				Maxi=j;
  34. 			}
  35. 		label[Maxi]=i;
  36. 		Q[i]=Maxi;
  37. 		for (vector<int>::iterator it=G[Maxi].begin();it!=G[Maxi].end();it++)
  38. 			if (label[*it]==0) Cnt[*it]++;
  39. 	}
  40. 	int ans=1;
  41. 	for (int k=n;k>=1;k--){
  42. 		int i=Q[k];
  43. 		F[i]=1;
  44. 		L.clear();
  45. 		for (vector<int>::iterator it=G[i].begin();it!=G[i].end();it++)
  46. 			if (label[*it]>label[i]) F[i]++;
  47. 		ans=max(ans,F[i]);
  48. 	}
  49. 	printf("%d\n",ans);
  50. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/vqJlV
language:
C++ (gcc 8.3)
created:
13 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!