Advertisement
Guest User

Untitled

a guest
Feb 19th, 2017
77
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 1.21 KB | None | 0 0
  1. #include <iostream>
  2. #include <queue>
  3. #include <cmath>
  4. using namespace std;
  5. int c[51],used[51],n,m,say=0,e=0,sum=0,syw,maxi;
  6. char adj[51][51];
  7. int dfs(int s){
  8. c[s]=2;
  9. say++;
  10. for(int i=1;i<=n;i++){
  11. if(c[i]==0 && adj[s][i]=='1'){
  12. dfs(i);
  13. }
  14. }
  15. }
  16. int main()
  17. {
  18. while(cin>>n){
  19. for(int i=1;i<=n;i++){
  20. for(int j=1;j<=n;j++){
  21. cin>>adj[i][j];
  22. if(adj[i][j]=='1'){
  23. e++;
  24. }
  25. }
  26. }
  27. e/=2;
  28. cin>>m;
  29. int uu;
  30. for(int i=1;i<=m;i++){
  31. cin>>uu;
  32. c[uu+1]=1;
  33. }
  34. for(int i=1;i<=n;i++){
  35. if(c[i]==1){
  36. say=0;
  37. dfs(i);
  38. maxi=max(say,maxi);
  39. sum+=say*(say-1)/2;
  40. }
  41. }
  42. for(int i=1;i<=n;i++){
  43. if(c[i]==0){
  44. syw++;
  45. }
  46. }
  47. if(syw!=0)
  48. syw+=maxi;
  49.  
  50. int res=sum-e+syw*(syw-1)/2,flag=0;;
  51. for(int i=1;i<=n;i++){
  52. if(c[i]==0){
  53. flag=1;
  54. }
  55. }
  56. if (flag==1)
  57. {
  58. res-=maxi*(maxi-1)/2;
  59. }
  60. cout<<res<<endl;
  61. maxi=syw=sum=say=e=0;
  62. for(int i=1;i<=n;i++)
  63. c[i]=0;
  64. }
  65. return 0;
  66. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement