mohammedehab2002

Untitled

Dec 2nd, 2020
627
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. bool vis[105];
  4. vector<pair<int,int> > ans;
  5. vector<int> s[2];
  6. int n,m,c[105],mat[105][105];
  7. bool dfs(int node,int cc)
  8. {
  9.     if (c[node]!=-1)
  10.     return (c[node]==cc);
  11.     c[node]=cc;
  12.     s[cc].push_back(node);
  13.     bool ok=1;
  14.     for (int i=1;i<=n;i++)
  15.     {
  16.         if (mat[node][i])
  17.         ok&=dfs(i,!cc);
  18.     }
  19.     return ok;
  20. }
  21. void add(int a,int b)
  22. {
  23.     ans.push_back({a,b});
  24.     mat[a][b]^=1;
  25.     mat[b][a]^=1;
  26. }
  27. void star(int r)
  28. {
  29.     for (int i=1;i<=n;i++)
  30.     {
  31.         if (i!=r)
  32.         add(r,i);
  33.     }
  34. }
  35. void star(int r,int a,int b)
  36. {
  37.     for (int i=1;i<=n;i++)
  38.     {
  39.         if (i!=r && i!=b)
  40.         add(r,i);
  41.     }
  42.     add(a,b);
  43. }
  44. int getleaf(int node)
  45. {
  46.     vis[node]=1;
  47.     for (int i=1;i<=n;i++)
  48.     {
  49.         if (mat[node][i] && !vis[i])
  50.         return getleaf(i);
  51.     }
  52.     return node;
  53. }
  54. void solve(int node,int p)
  55. {
  56.     vis[node]=1;
  57.     for (int i=1;i<=n;i++)
  58.     {
  59.         if (mat[node][i] && !vis[i])
  60.         solve(i,node);
  61.     }
  62.     int cur=0;
  63.     for (int i=1;i<=n;i++)
  64.     {
  65.         if (i==p)
  66.         continue;
  67.         if (mat[node][i])
  68.         {
  69.             if (!cur)
  70.             cur=i;
  71.             else
  72.             {
  73.                 star(node,cur,i);
  74.                 star(node,i,cur);
  75.                 cur=0;
  76.             }
  77.         }
  78.     }
  79.     if (mat[node][p] && cur)
  80.     {
  81.         star(node,cur,p);
  82.         star(node,p,cur);
  83.     }
  84. }
  85. int main()
  86. {
  87.     freopen("xot.in", "r", stdin);
  88.     scanf("%d",&n);
  89.     for (int i=1;i<=n;i++)
  90.     {
  91.         for (int j=1;j<=n;j++)
  92.         {
  93.             scanf("%d",&mat[i][j]);
  94.             m+=mat[i][j];
  95.         }
  96.     }
  97.     m/=2;
  98.     if (n%2 && m%2)
  99.     {
  100.         printf("-1");
  101.         return 0;
  102.     }
  103.     memset(c,-1,sizeof(c));
  104.     if (dfs(1,0) && s[0].size()*s[1].size()==m)
  105.     {
  106.         for (int i:s[0])
  107.         star(i);
  108.         goto out;
  109.     }
  110.     if (m%2)
  111.     star(getleaf(1));
  112.     memset(vis,0,sizeof(vis));
  113.     solve(1,0);
  114.     out:
  115.     printf("%d\n",ans.size()/(n-1));
  116.     for (auto p:ans)
  117.     printf("%d %d\n",p.first,p.second);
  118. }
RAW Paste Data