Codeforces #360 C. NP-Hard Problem
传送门：http://codeforces.com/contest/688/problem/C
题目大意
一张图，问是否可以把点分为两个不交叉的集合（可以有点两个集合都不属于），使每条边的两个点属于不同集合。
输入 n , m 表示 n 个点， m 条边。
接下来 m 行，每行两个数，表示一条边。
分别输出两个集合的大小与集合包含点。
题解
二分图判定&输出
DFS染色即可
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 |
#include<cstdio> using namespace std; const int Maxn=100000+5; struct Edge{ int v,nxt; Edge(){} Edge(int v0,int n0){ v=v0; nxt=n0; } }; Edge e[Maxn*2]; int head[Maxn]; int nume; inline void addEdge(int x,int y){ e[++nume]=Edge(y,head[x]); head[x]=nume; } int col[Maxn]; int inE[Maxn]; int n,m; bool flag=true; int cnt1=0,cnt2=0; void dfs(int x,int colo){ if (colo==1) { cnt1++; col[x]=1; }else{ cnt2++; col[x]=-1; } for (int i=head[x];i;i=e[i].nxt){ int v=e[i].v; if (col[v]==0){ dfs(v,col[x]*-1); }else if (col[v]*col[x]==-1){ //do nothing }else{ flag=false; return ; } if (flag==false) return; } } int main(){ scanf("%d%d",&n,&m); for (int i=1;i<=m;i++){ int x,y; scanf("%d%d",&x,&y); addEdge(x,y);addEdge(y,x); inE[x]++;inE[y]++; } for (int i=1;i<=n;i++){ if (col[i]==0 && inE[i]!=0) dfs(i,1); } if(flag==true){ printf("%d\n",cnt1); for (int i=1;i<=n;i++) if (col[i]==1) printf("%d ",i); printf("\n"); printf("%d\n",cnt2); for (int i=1;i<=n;i++) if (col[i]==-1) printf("%d ",i); printf("\n"); }else{ printf("-1\n"); } return 0; } |
原文链接：Codeforces #360 C. NP-Hard Problem
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!