题解 CF687A 【NP-Hard Problem】

Zenith_Yeh · 2020-08-12 11:21:41 · 题解

这道题其实是二分图判定的裸题，在此我用我认为较简单的算法 DFS 来判定二分图即可。

就是把 CZ和面包 看成两种颜色，然后进行二分图判定即可。

上菜：

#include<bits/stdc++.h> 
using namespace std;
int n,m,u,v,co[100010],blk,wht;
bool vis[100010];
vector<int> a[100010];
bool dfs(int now,int color)//DFS判定。
{   vis[now]=true;co[now]=-color;
    bool ok=true;
    for(int i=0;i<a[now].size();i++)//枚举与它相连的点。
    {   if(!vis[a[now][i]])ok&=dfs(a[now][i],-color);//判定。
        else ok&=(co[now]!=co[a[now][i]]);
    }
    return ok;
}
int main()
{   scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++)
    {   scanf("%d%d",&u,&v);
        a[u].push_back(v);a[v].push_back(u);//加点。
    }
    for(int i=1;i<=n;i++)
    {   if(!vis[i])//DFS判定。
        {   if(!dfs(i,-1))
            {   printf("-1");
                return 0;
            }
        }
    }
    for(int i=1;i<=n;i++)if(co[i]>0)blk++;//记一下。
    wht=n-blk;printf("%d\n",blk);
    for(int i=1;i<=n;i++)
    {   if(co[i]>0)
        {   printf("%d",i);
            if(--blk)printf(" ");
        }
    }
    cout<<endl;printf("%d\n",wht);
    for(int i=1;i<=n;i++)
    {   if(co[i]<0)
        {   printf("%d",i);
            if(--wht)printf(" ");
        }
    }
    return 0;
}