Constructions of E and Isomorphism of Complementary Maps in the Multi-school Training Camp of Niuke in Summer of 2019 (Game 6)

https://ac.nowcoder.com/acm/contest/886#question

Question: Whether there exists an undirected graph G with n vertices is the isomorphism of its complement graph H, if there exists an adjacency matrix of output G and the mapping of H with respect to G.

Analytical and constructive questions, the answer is not unique. The original graph has the same number of edges as the complementary graph, so there is no solution when n=4*k+2 and 4*k+3

When n=4*k, the points are divided into four parts: P1,P2,P3,P4. The first two parts of P1P2 are all connected by two sides of the points, the two sides between the parts of P3P1 and the parts, and the two sides between the parts of P4P2.

Its complementary graph is composed of groups of P3P4, edges between P4P1 and P3P2, which are isomorphic to the original graph.

Mapping relationship between blocks, original P1P2P3P4 complement P3P4P2P1 or other schemes.

Code

//B
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 2e3+10;
int g[maxn][maxn];
int main()
{
    int t,n,kase=1;
    cin>>t;
    while(t--){
        cin>>n;
        memset(g,0,sizeof(g));
        printf("Case #%d: ",kase++);
        if(n%4==2||n%4==3){
            cout<<"No"<<endl;
            continue;
        }
        else {
            cout<<"Yes"<<endl;
            int block=n/4;
            for(int i=1;i<=block;i++){
                for(int j=block+1;j<=2*block;j++)
                    g[i][j]=g[j][i]=1;
                for(int j=2*block+1;j<=3*block;j++)
                    g[i][j]=g[j][i]=1;
                for(int j=i+1;j<=block;j++)
                    g[i][j]=g[j][i]=1;
            }
            for(int i=block+1;i<=2*block;i++){
                for(int j=3*block+1;j<=4*block;j++)
                    g[i][j]=g[j][i]=1;
                for(int j=i+1;j<=2*block;j++)
                    g[i][j]=g[j][i]=1;
            }
            if(n%4==1){
                for(int i=1;i<=2*block;i++)
                    g[i][n]=g[n][i]=1;
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++)
                        printf("%d",g[i][j]);
                    printf("\n");
                }
                for(int i=2*block+1;i<=4*block;i++)
                    printf("%d ",i);
                for(int i=2*block;i>=1;i--)
                    printf("%d ",i);
                printf("%d\n",n);
            }
            else{
                for(int i=1;i<=n;i++){
                    for(int j=1;j<=n;j++)
                        printf("%d",g[i][j]);
                    printf("\n");
                }
                for(int i=2*block+1;i<=4*block;i++)
                    printf("%d ",i);
                for(int i=2*block;i>=1;i--)
                    printf("%d%c",i,i==1?'\n':' ');
            }
        }

    }
}

Tags: Linux P4

Posted on Thu, 10 Oct 2019 11:30:23 -0700 by kirtan007