7/27 (board) dyeing method to determine bipartite graph + find combination number (recursive formula)

1. Determine bipartite graph by coloring

Given a  nn  A little bit  mm  Undirected graph of strip and edge , There may be double edges and self rings in the graph .

Please judge whether this graph is bipartite .

Input format

The first line contains two integers  nn  and  mm.

Next  mm  That's ok , Each line contains two integers  uu  and  vv, Indication point  uu  Sum point  vv  There is an edge between .

Output format

If a given graph is a bipartite graph , The output  Yes, Otherwise output  No.

Data range

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

sample input ：

4 4
1 3
1 4
2 3
2 4

sample output ：

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()
{
    // Salted eggs _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. Find the combination number i（ Pay attention to the data range ）

Given  nn  Group inquiry , Each group is given two integers  a,ba,b, Please output  Cbamod(109+7)Cabmod(109+7)  Value .

Input format

The first line contains integers  nn.

Next  nn  That's ok , Each line contains a set of  aa  and  bb.

Output format

common  nn  That's ok , Each line outputs a solution to the query .

Data range

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

sample input ：

3
3 1
5 3
2 2

sample output ：

3
10
1

Ideas ： According to the recursive formula of combination number, preprocessing in advance is 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;
}