现金酬谢!关于图的二着色的问题,C语言大手子帮帮我

发布网友发布时间：2022-05-26 11:07

我来回答

共3个回答

热心网友时间：2023-10-14 11:43

1、描述一下具体输入，比如上图一，长这样？？还是邻接矩阵？还是直接一堆边？

5
4 2
1 5
5
1 5
2 3 4

2、你这个问题本质上属于二分图染色。。你可以百度找一下资料

我写过二分图匹配的题可以参考，，，。提交：

代码网页链接

//二分图最大匹配 O(V*E) Test#include<iostream>#include<vector>#include<cstring>using namespace std;const int N = 3e6;vector<int>G[N];int po[N], book[N], ans;int find(int u){
    for(int i = 0; i < G[u].size(); i++){
        int v = G[u][i];
        if(!book[v]){
            book[v] = 1;
            if(po[v]==0||find(po[v])){
                po[v] = u;
                return true;
            }
        }
    }
    return false;}int main(){
    int nl, nr, m;
    cin>>nl>>nr>>m;
    for(int i = 1; i <= m; i++){
        int x, y;  cin>>x>>y;
        G[y].push_back(x);
    }
    for(int i = 1; i <= nr; i++){
        memset(book,0,sizeof(book));
        if(find(i)){
            ans++;
        }
    }
    cout<<ans<<"\n";
    for(int i = 1; i <= nl; i++)cout<<po[i]<<" ";
    return 0;}

热心网友时间：2023-10-14 11:44

需要画出着色的图嘛？

热心网友时间：2023-10-14 11:44

出多少