LOJ #10097. 「一本通 3.5 练习 5」和平委员会
传送门
GDOI
根据2−SAT套路,我们要把这个问题转换成依赖性问题,即选择u,就必须选v。
这个也是非常好转化的,假设i,j互相憎恶,因为每个党派都必须有一个代表,所以选择了i就必须选择j所在的党派的另一人,同理,选择了j就必须选择i所在党派的另一人。
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
| #include <bits/stdc++.h> #define MAXN 2000005 using namespace std; inline int read(){ int x=0,f=1; char ch=getchar(); while (ch<'0'||ch>'9'){ if (ch=='-') f=-1; ch=getchar(); } while (ch>='0'&&ch<='9'){ x=(x<<3)+(x<<1)+(ch^'0'); ch=getchar(); } return x*f; } vector<int>G[MAXN]; inline void AddEdge(int u,int v){ G[u].push_back(v); } int dfn[MAXN],low[MAXN],cnt; stack<int>stk; int scc,col[MAXN]; void tarjan(int u){ dfn[u]=low[u]=++cnt; stk.push(u); for (register int i=0;i<G[u].size();++i){ int v=G[u][i]; if (!dfn[v]) tarjan(v),low[u]=min(low[u],low[v]); else if (!col[v]) low[u]=min(low[u],dfn[v]); } if (low[u]==dfn[u]){ ++scc; do{ col[u]=scc; u=stk.top(),stk.pop(); }while (low[u]!=dfn[u]); } } inline int Other(int x){ if (x%2==0) return x-1; else return x+1; } int main(){ int n=read(),m=read(); for (register int i=1;i<=m;++i){ int u=read(),v=read(); AddEdge(u,Other(v)); AddEdge(v,Other(u)); } for (register int i=1;i<=(n<<1);++i){ if (!dfn[i]) tarjan(i); } for (register int i=1;i<=n;++i){ if (col[i*2-1]==col[i*2]){ puts("NIE"); return 0; } } for (register int i=1;i<=n;++i){ int u=i*2-1,v=i*2; if (col[u]<col[v]) printf("%d\n",u); else printf("%d\n",v); } }
|