题解 P1657 【选书】

孙广宸 · 2018-08-24 15:23:14 · 题解

简单搜索板子题，具体内容看代码

#include<bits/stdc++.h>
using namespace std;
int love[10001][2],tot=0;
int n;
int flag[10001]={false};
void dfs(int num)
{
    if(num==n+1)//超过n就代表搜完了
    {
        tot++;
        return;
    }
    if(!flag[love[num][0]])//case1
    {
        flag[love[num][0]]=true;
        dfs(num+1);
        flag[love[num][0]]=false;
    }
    if(!flag[love[num][1]])//case2
    {
        flag[love[num][1]]=true;
        dfs(num+1);
        flag[love[num][1]]=false;
    }
    //千万别忘记回溯哦QAQ
}
int main()
{
    cin>>n;
    if(n==0)
    {
        cout<<0;
        return 0;
    }//这个特判可以说是特别的恶心qwq
    for(int i=1;i<=n;i++)
        cin>>love[i][0]>>love[i][1];
    dfs(1);
    cout<<tot;
    return 0;
}