题目链接:http://codeforces.com/problemset/problem/555/E
给定N个节点和M条无向边,再给出Q对(u,v),问能否给每条边标上方向,使Q中的u节点都能到达v节点。
很明显,一个强连通分量中的点只要连成一个点,就一定可以相互到达,tarjan缩点之后整张图就变成了一棵树或者森林。然后可以拿树链剖分对每对(u,v)需要标记的边做线段覆盖,如果一条线段被两个方向的线段树同时覆盖,就说明不存在方案。
#include <cstdio> #include <cstring> #include <algorithm> #include <vector> #include <stack> using namespace std; const int MaxN = 200003; typedef vector<int> vec; typedef vec::iterator iter; int n,m,q; vec e[MaxN],g[MaxN]; int low[MaxN],dfn[MaxN],tarjan_index; bool visited[MaxN],instk[MaxN]; stack<int> stk; int blocks,b[MaxN]; void tarjan(int x,int father) { low[x]=dfn[x]=++tarjan_index; visited[x]=true; stk.push(x);instk[x]=true; bool flag=true; for (iter i=e[x].begin();i!=e[x].end();i++) { if (flag && *i==father) { flag=false; continue; } if (!visited[*i]) { tarjan(*i,x); low[x]=min(low[x],low[*i]); } else if (instk[*i]) low[x]=min(low[x],dfn[*i]); } if (low[x]==dfn[x]) { blocks++; int t; do { t=stk.top();stk.pop(); instk[t]=false; b[t]=blocks; } while (t!=x); } } int fa[MaxN],sz[MaxN],dep[MaxN],head[MaxN],id[MaxN],tnum[MaxN]; void build(int x) { sz[x]=1; for (iter i=g[x].begin();i!=g[x].end();i++) { if (*i==fa[x]) continue; fa[*i]=x; dep[*i]=dep[x]+1; tnum[*i]=tnum[x]; build(*i); sz[x]+=sz[*i]; } } int partid; void part(int x) { id[x]=++partid; int p=-1; if (head[x]==0) head[x]=x; for (iter i=g[x].begin();i!=g[x].end();i++) { if (*i==fa[x]) continue; if (sz[*i]>sz[p]) p=*i; } if (p==-1) return; head[p]=head[*i]; part(p); for (iter i=g[x].begin();i!=g[x].end();i++) { if (*i==fa[x] || *i==p) continue; part(*i); } } bool up[MaxN << 2],down[MaxN << 2]; void cover(bool* s,int p,int l,int r,const int& ll,const int& rr) { if (ll<=l && r<=rr) s[p]=true; if (s[p]) return; int mid=(l+r)/2; if (ll<=mid) cover(s,p*2,l,mid,ll,rr); if (rr>mid) cover(s,p*2+1,mid+1,r,ll,rr); } inline void cover(bool* s,int l,int r) { cover(s,1,1,blocks,l,r); } inline bool getx(bool* s,int x) { int p=1,l=1,r=blocks,mid; while (l<r) { if (s[p]) return true; mid=(l+r)/2; if (x<=mid) { p*=2; r=mid; } else { p=p*2+1; l=mid+1; } } return s[p]; } inline void deal(int u,int v) { int t; while (u!=v) { if (head[u]==head[v]) { if (dep[u]<dep[v]) cover(down,id[u]+1,id[v]); else cover(up,id[v]+1,id[u]); u=v; break; } if (dep[u]<dep[v]) { t=head[v]; if (fa[t]==t) cover(down,id[t]+1,id[v]); else cover(down,id[t],id[v]); v=fa[t]; } else { t=head[u]; if (fa[t]==t) cover(up,id[t]+1,id[u]); else cover(up,id[t],id[u]); u=fa[t]; } } } int main() { //freopen("555E.in","r",stdin); //freopen("555E.out","w",stdout); scanf("%d%d%d",&n,&m,&q); int u,v; for (int i=1;i<=m;i++) { scanf("%d%d",&u,&v); e[u].push_back(v); e[v].push_back(u); } for (int i=1;i<=n;i++) if (!visited[i]) tarjan(i,i); for (int i=1;i<=n;i++) for (iter j=e[i].begin();j!=e[i].end();j++) if (b[i]!=b[*j]) { g[b[i]].push_back(b[*j]); g[b[*j]].push_back(b[i]); } for (int i=1;i<=blocks;i++) { sort(g[i].begin(),g[i].end()); g[i].erase(unique(g[i].begin(),g[i].end()),g[i].end()); } int cnt=0; for (int i=1;i<=blocks;i++) if (tnum[i]==0) { tnum[i]=++cnt; dep[i]=1; fa[i]=i; build(i); part(i); } for (int i=1;i<=q;i++) { scanf("%d%d",&u,&v); if (tnum[b[u]]!=tnum[b[v]]) goto fail; deal(b[u],b[v]); } for (int i=1;i<=blocks;i++) if (getx(up,i) && getx(down,i)) goto fail; printf("Yes\n"); return 0; fail: printf("No\n"); return 0; }
2 条评论
厉害了zrj
太神了