7/27（板子）染色法判定二分图+求组合数（递推公式）

1.染色法判定二分图

给定一个 nn 个点 mm 条边的无向图，图中可能存在重边和自环。

请你判断这个图是否是二分图。

输入格式

第一行包含两个整数 nn 和 mm。

接下来 mm 行，每行包含两个整数 uu 和 vv，表示点 uu 和点 vv 之间存在一条边。

输出格式

如果给定图是二分图，则输出 Yes，否则输出 No。

数据范围

1≤n,m≤1051≤n,m≤105

输入样例：

4 4
1 3
1 4
2 3
2 4

输出样例：

Yes

#include <bits/stdc++.h>
using namespace std;
const int N=200010;
int n,m;
int color[N];
int he[N],e[N],ne[N],idx;
void add(int a,int b)
{
    e[idx]=b;
    ne[idx]=he[a];
    he[a]=idx++;
}
bool dfs(int u,int c)
{
    color[u]=c;
    for(int i=he[u];i!=-1;i=ne[i])
    {
        int j=e[i];
        if(!color[j])
        {
            if(!dfs(j,3-c))
                return false;
        }
        else if(color[j]==c)
            return false;
    }
    return true;
}
int main()
{
    //咸蛋_dd salty egg
    scanf("%d %d",&n,&m);
    memset(he,-1,sizeof(he));
    while(m--)
    {
        int a,b;
        cin>>a>>b;
        add(a,b);
        add(b,a);
    }
    bool flag=true;
    for(int i=1;i<=n;i++)
    {
        if(!color[i])
        {
            if(!dfs(i,1))
            {
                flag=false;
                break;
            }
        }
    }
    if(flag)
        puts("Yes");
    else
        puts("No");
    return 0;
}

 2.求组合数i（注意数据范围）

给定 nn 组询问，每组询问给定两个整数 a，ba，b，请你输出 Cbamod(109+7)Cabmod(109+7) 的值。

输入格式

第一行包含整数 nn。

接下来 nn 行，每行包含一组 aa 和 bb。

输出格式

共 nn 行，每行输出一个询问的解。

数据范围

1≤n≤100001≤n≤10000,
1≤b≤a≤20001≤b≤a≤2000

输入样例：

3
3 1
5 3
2 2

输出样例：

3
10
1

思路：根据组合数的递推公式提前预处理就ok了

#include <bits/stdc++.h>
using namespace std;
const int N=2010,mod=1e9+7;
int c[N][N];
void init()
{
    for(int i=0;i<N;i++)
        for(int j=0;j<=i;j++)
        if(!j)c[i][j]=1;
        else c[i][j]=(c[i-1][j]+c[i-1][j-1])%mod;
}
int main()
{
    int n;
    init();
    scanf("%d",&n);
    while(n--)
    {
        int a,b;
        scanf("%d %d",&a,&b);
        printf("%d\n",c[a][b]);
    }
    return 0;
}