fork download 
  1. #include <cstdio>
  2. #include <cstring>
  3. #include <iostream>
  4. #include <algorithm>
  5. #include <vector>
  6. #include <set>
  7. using namespace std;
  8.  
  9. const int N=1005;
  10.  
  11. int n,m;
  12. int label[N];
  13. int Cnt[N];
  14. int mat[N][N];
  15. int Q[N];
  16. vector <int> vec;
  17.  
  18. bool check(){
  19. 	for (int i=1;i<=n;i++){
  20. 	    vec.clear();
  21. 		for (int j=1;j<=n;j++)
  22. 			if (mat[i][j] && label[j]>label[i])
  23. 				vec.push_back(j);
  24. 		for (int j=1;j<vec.size();j++)
  25. 			if (label[vec[j]]<label[vec[0]])
  26. 				swap(vec[j],vec[0]);
  27. 		for (int j=1;j<vec.size();j++)
  28. 			if (!mat[vec[0]][vec[j]]) return false;
  29. 	}
  30. 	return true;
  31. }
  32.  
  33. int main(){
  34. 	while (1){
  35. 		scanf("%d%d",&n,&m);
  36. 		if (!n && !m) break;
  37. 		memset(mat,0,sizeof(mat));
  38. 		for (int i=0;i<m;i++){
  39. 			int x,y;
  40. 			scanf("%d%d",&x,&y);
  41. 			mat[x][y]=mat[y][x]=1;
  42. 		}
  43. 		for (int i=1;i<=n;i++) Cnt[i]=label[i]=0;
  44. 		for (int i=n;i>=1;i--){
  45. 			int Max=-1;
  46. 			int Maxi=-1;
  47. 			for (int j=1;j<=n;j++)
  48. 				if (!label[j] && Cnt[j]>Max){
  49. 					Max=Cnt[j];
  50. 					Maxi=j;
  51. 				}
  52. 			label[Maxi]=i;
  53. 			Q[i]=Maxi;
  54. 			for (int j=1;j<=n;j++)
  55. 				if (label[j]==0 && mat[Maxi][j])
  56. 					Cnt[j]++;
  57. 		}
  58. 		if (check()) printf("Perfect\n\n");
  59. 		        else printf("Imperfect\n\n");
  60. 	}
  61. }
Not running #stdin #stdout 0s 0KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/8QX5e
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!