ACdream 1056 Bad Horse (判断二分图)（并查集 or BFS）

港控/mmm° 2022-06-14 01:55 149阅读 0赞

题目链接：  
[ACdream 1056][]

题解：  
其实就是让你判断是否是一个二分图。  
随便做….BFS or dsu （并查集）。  
我都写一个吧。

BFS代码：

/*
    * this code is made by LzyRapx
    * Problem: 1056
    * Verdict: Accepted
    * Submission Date: 2017-06-06 22:53:47
    * Time: 68MS
    * Memory: 1704KB
    */
    #include <bits/stdc++.h>
    using namespace std;
    map<string,int>color;
    map<string,vector<string> >G;
    
    int bfs(string source)
    {
        string u,v;
        u=source;
        color[source] = 1;
        queue<string>q;
        q.push(source);
    
        while(!q.empty())
        {
            u = q.front();
            q.pop();
            for(int i=0;i<G[u].size();i++)
            {
                v = G[u][i];
                if(color[v] == -1 && color[u] != color[v])
                {
                    color[v] = 1-color[u];
                    q.push(v);
                }
                else if (color[v] == color[u])
                {
                    return 0;
                }
            }
        }
        return 1;
    } 
    int main()
    {
        int cas=1,t;
        cin>>t;
        int n;
        string s1,s2;
        while(t--)
        {
            cin>>n;
            G.clear();
            color.clear();
            for(int i=1;i<=n;i++)
            {
                cin>>s1>>s2;
                G[s1].push_back(s2);
                G[s2].push_back(s1);
                color[s1]=color[s2]=-1;
            }
            printf("Case #%d: ",cas++);
            if(bfs(color.begin()->first))
            {
                puts("Yes");
            }
            else{
                puts("No");
            }
        }
        return 0;
    }

DSU代码：

/*
    * this code is made by LzyRapx
    * Problem: 1056
    * Verdict: Accepted
    * Submission Date: 2017-06-06 23:08:08
    * Time: 36MS
    * Memory: 1684KB
    */
    #include <bits/stdc++.h>
    using namespace std;
    map<string,int>color;
    int fa[456];
    int getfather(int x)
    {
        return fa[x]==x?x:fa[x]=getfather(fa[x]);
    }
    
    void Merge(int a,int b)
    {
        int p1=getfather(a);
        int p2=getfather(b);
        fa[p1] = p2;
    }
    int main()
    {
        int cas=1,t;
        cin>>t;
        int n;
        string s1,s2;
        while(t--)
        {
            int flag = 1;
            color.clear();
            int t = 1;
            cin>>n;
            n<<=1;
            for(int i=1;i<=n;i++)fa[i]=i;
            n>>=1;
            for(int i=1;i<=n;i++)
            {
                cin>>s1>>s2;
                if(flag==0)continue;
                if(color[s1]==0) color[s1] = t++;
                if(color[s2]==0) color[s2] = t++;
                if(getfather(color[s1]) != getfather(color[s2]) )
                {
                    Merge(color[s1],n+color[s2]);
                    Merge(color[s1]+n,color[s2]);
                }
                else
                {
                    flag = 0;
                }
            }
            printf("Case #%d: ",cas++);
            puts(flag?"Yes":"No");
        }
        return 0;
    }

[ACdream 1056]: http://acdream.info/problem?pid=1056