C++14 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2020-07-15

#include <stdio.h>
#include <string.h>
struct node
{
       int x;
       int y;
};
int m;
int flag1=0;
struct node a[100];
int b[101][101];
int c[100];
int a1[101],a2[101];
void init()
{
       int i,j;
       for(i=1;i<=100;i++)
       {
              for(j=1;j<=100;j++)
              {
                     b[i][j]=0;
              }
       }
}
void init2()
{
       int i;
       for(i=1;i<=100;i++)
       {
              a1[i]=0;
              a2[i]=0;
       }
}
void qiongju(int m1)
{
       if(m1==m)
       {
            int i,j;
            int flag=1;
            int n1=1,n2=1;
            init2();
            for(i=1;i<=m;i++)
            {
                   if(c[i-1]==0)
                   {
                          a1[n1]=i;
                          n1++;
                   }
                    if(c[i-1]==1)
                   {
                          a2[n2]=i;
                          n2++;
                   }
            }
            for(i=1;i<=m;i++)
            {
                   for(j=1;j<=m;j++)
                   {
                        if(b[a1[i]][a1[j]]==1||b[a2[i]][a2[j]]==1)
                        {
                               flag=0;
                        }
                   }
            }
             if(flag==1)
             {
              flag1=1;
             }
       }
       else
       {
              c[m1]=0;
              qiongju(m1+1);
              c[m1]=1;
              qiongju(m1+1);
       }
}
int main()
{
       int i,j;
       int n;
       init();
       scanf("%d %d",&m,&n);
       for(i=0;i<n;i++)
       {
              scanf("%d%d",&a[i].x,&a[i].y);
       }
       for(i=1;i<=m;i++)
       {
             for(j=0;j<n;j++)
             {
                    if(a[j].x==i)
                    {
                           b[i][a[j].y]=1;
                    }
             }
       }
       qiongju(0);
       if(flag1==1)
       {
              printf("1\n");
       }
       else
              printf("0\n");
       return 0;
}

C++ 解法, 执行用时: 2ms, 内存消耗: 376KB, 提交时间: 2020-12-16

#include<iostream>
#include <vector>
#include <map>
using namespace std;
int main()
{
    int tol;
    int req_num;
    cin>>tol;
    cin>>req_num;
    vector<vector<int>> require(req_num,vector<int>(2,0));
    for(int i=0;i<req_num;i++){
        cin>>require[i][0]>>require[i][1];
    }
    //数据处理
    int res=1;
     map<int,int> classify;
    for(auto req:require)
    {
        if(classify[req[0]]>0&&classify[req[0]]==classify[req[1]]) 
        {
           res=0;
            break;
        }
        if(classify[req[0]]>0) classify[req[1]]=3-classify[req[0]];
        else if(classify[req[1]]>0) classify[req[0]]=3-classify[req[1]];
        else {
            classify[req[0]]=1;
            classify[req[1]]=2;
        }
    }
    cout<<res<<endl;
    return 0;
}