Code shoe set - mt3435 · assignment - bipartite graph problem - Graphic explanation

---

assignment

• assignment .

The time limit ：1 second
Space restriction ：256M

---

Title Description

Given a picture containing n Nodes m Undirected graph of strip and edge , You must assign a point weight to each point （ Must be 1 2 3 One of them ）, How many different assignment methods are there （ Isn't that what 3^n Do you ？？？, To look down ）

But there is one limitation ： That is, the parity of the two endpoints of each edge must be different

---

Input description

Enter two integers on the first line n,m

Next m Two integers per line u,v representative u and v There is a side between

（ Data guarantees that there is no self loop , There is no double edge , It is not guaranteed to be a connected graph ）

（1<=n,m<=300000,1<=u,v<=n)

---

Output description

Enter the total number of schemes , The answer could be very big , The result is right 1e9+7 modulus

---

Example 1

Input

4 4
1 2
2 3
3 4
1 4

Output

8

Topic analysis

Brief description of bipartite graph

This problem is essentially a bipartite graph problem .

Bipartite graph is to divide all nodes of a graph into two sets $A$、$B$ in , So that the nodes at both ends of each edge are not in a set .

informally , All red nodes cannot have edges directly connected , All blue nodes cannot have edges directly connected .

If we divide a connected graph into the above set $A$ and $B$, Then we can put $A$ All nodes in are assigned odd numbers ,$B$ All nodes in the are assigned an even number .

Because odd numbers have $1$ and $3$ Two kinds of , Even numbers only $2$ This kind of , So the number of assignment schemes is $2^a$, among $a$ yes $A$ Number of nodes in .

Empathy , We can also put $A$ The nodes in the are assigned an even number ,$B$ The nodes in the are assigned an odd number , Then there are $2^b$ Two assignment schemes , among $b$ Is a collection $B$ Number of nodes in .

in summary , One can divide nodes into sets $A$ and $B$ The bipartite graph of , The node is assigned as $1、2、3$ The assignment scheme with different parity of adjacent nodes is $2^a+2^b$

Then the problem becomes how to divide the given graph into different bipartite graphs .

Divided into bipartite graphs

We can use $color[i]$ Representation node $i$ Grouping of .$0$ Represents a group ,$1$ Represents that the node is divided into sets $A$ in ,$2$ The delegate is divided into sets $B$ in .

Traverse every node , If this node has not been partitioned , Take this node as a new bipartite graph “ Source point ”,$BFS$ Go over and count the set of subgraphs $A、B$ The number of nodes in .

Be careful ： if $BFS$ In the process, I found “ The nodes at both ends of an edge belong to the same set ” The situation of , The graph cannot be divided into bipartite graphs , The number of assignment schemes is $0$.（ As shown by the green edge in the following figure ）

It turns out that

When we divide this graph into different bipartite graphs , The product of the number of schemes of each bipartite graph , Is the total number of schemes .

For specific implementation, please refer to code comments

AC Code

//  Given a picture containing n Nodes m Undirected graph of strip and edge , The parity of the two endpoints of each edge must be different , How many different assignment methods are there 
#include <bits/stdc++.h>
using namespace std;
#define mem(a) memset(a, 0, sizeof(a))
#define dbg(x) cout << #x << " = " << x << endl
#define fi(i, l, r) for (int i = l; i < r; i++)
#define cd(a) scanf("%d", &a)
typedef long long ll;

const ll mod = 1e9 + 7;
vector<int> a[300010];  //  Save map 
ll Pow[300010] = {
    1};  // Pow[i] = 2^i
int color[300010] = {
    0};  //  Grouping , The default value is 0 Indicates ungrouped 

int main() {
    
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
      //  Preprocessing , Calculation 2^i
        Pow[i] = (Pow[i - 1] * 2) % mod;
    }
    for (int i = 0; i < m; i++) {
      //  Read in the picture 
        int l, r;
        scanf("%d%d", &l, &r);
        a[l].push_back(r);
        a[r].push_back(l);
    }
    ll ans = 1;  //  answer 
    for (int i = 1; i <= n; i++) {
      //  Traverse all nodes 
        if (!color[i]) {
      //  Not dyed yet （ The description has not been divided into some sub graph ）
            int aNode = 0, bNode = 0;  //  Bipartite graph A、B The number of nodes in 
            queue<int> q;  // bfs queue 
            function<void(int, int)> addOneNode = [&](int thisNode, int thisColor) {
      //  Handle a new node 
                color[thisNode] = thisColor;  //  Label grouping 
                q.push(thisNode);  //  The team 
                if (thisColor == 1)  //  Count the number of nodes in the set 
                    aNode++;
                else
                    bNode++;
            };
            addOneNode(i, 1);  //  Let's deal with the... Of this subgraph first “ Source point ”
            while (q.size()) {
      //  Start BFS
                int thisNode = q.front();
                q.pop();  //  Team leader 
                int toColor = (color[thisNode] == 1 ? 2 : 1);  //  The set to which its adjacent nodes belong 
                for (int& toNode : a[thisNode]) {
      //  Traverse all the edges of this node 
                    if (!color[toNode]) {
      //  Adjacent nodes have not been grouped 
                        addOneNode(toNode, toColor);  //  Handle this neighboring node （ Partition sets 、 The team 、 Statistics ）
                    }
                    else {
      //  This neighboring node has been grouped 
                        if (color[toNode] == color[thisNode]) {
      //  And this node is also divided into a group 
                            puts("0");  //  Can not be divided into bipartite graphs , The number of programmes is 0
                            return 0;
                        }
                    }
                }
            }
            ans = (ans * (Pow[aNode] + Pow[bNode])) % mod;  //  The product of the number of schemes of each subgraph 
        }
    }
    cout << ans << endl;
    return 0;
}

Update the weekly competition solution of elite class in advance every week , Focus , Neverlost

Originality is not easy. , Reprint please attach Link to the original text Oh ~
Tisfy：https://letmefly.blog.csdn.net/article/details/125537979