「泉七培训 – 刘定峰」链型网络
题意
给定一张无重边，自环的无向图
每次可以加边，或者询问有多少个点满足将该点删除后，原图的每个连通块都为一条链
数据范围
30%的数据n<=100 m<=2n
100%的数据n<=100000,m<=2n
题解
30分很简单
对于每次询问枚举删去每一个点，然后再用O（n）的时间在图上判环以及度数是否都小等于2
然后正解。。。
考虑以下一些简单的情况
原图为若干条链，则答案为点数N
原图为单个简单环加若干条链，则答案为环大小
原图中超过一个连通块有环，答案为0
原图中一个连通块为一个点连接三条链，答案为4，三棵树不是很容易确定
原图中一个连通块为一个点连接三条以上的链，答案为1
另外显然随着边的加入，答案不会增大
考虑链的性质，一个图的每个连通块为链，等价于每个点的度数小于等于2且无环
考虑图中如果存在一个度数大于等于3的点u, 因为要保证去掉一个点后每个点的度数都小于等于2，我们要么去掉u，要么在u度数恰好为3时，去掉u 的三个相邻点中的一个，而其他的点均不可能成为答案
这样我们只需要在加边过程中第一次出现度数为3的点的时候， 对于可能成为答案的4个点，分别维护一个去掉该点之后的图，然后询问在4个图中分别进行判断，若某个图中无环且无度数>=3的点，即图中连通块均为链，则ans++
实现只要用个带权并查集
30分
|
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 |
#include<iostream> #include<cstdio> #include<iostream> #include<cstdlib> #include<cstring> #include<ctime> #define ll long long using namespace std; //---------------------------------------------------------------- inline ll read() { ll 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*10+ch-'0';ch=getchar();} return x*f; } //----------------------------------------------------------------快速读入 int n,m,cnt; int d[100005],head[100005]; bool vis[100005]; struct data{int to,next;}e[200005]; void ins(int u,int v) { d[u]++;d[v]++; e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt; e[++cnt].to=u;e[cnt].next=head[v];head[v]=cnt; } bool dfs(int x,int f,int y) { vis[x]=1; for(int i=head[x];i;i=e[i].next) { if(e[i].to==f||e[i].to==y)continue; if(vis[e[i].to])return 0; else if(!dfs(e[i].to,f,x))return 0; } return 1; } bool jud(int x) { for(int i=1;i<=n;i++) if(i!=x&&d[i]>2)return 0; memset(vis,0,sizeof(vis)); for(int i=1;i<=n;i++) if(!vis[i]&&i!=x){if(!dfs(i,x,0))return 0;} return 1; } int getans() { int sum=0; for(int x=1;x<=n;x++) { for(int i=head[x];i;i=e[i].next) d[e[i].to]--; if(jud(x))sum++; for(int i=head[x];i;i=e[i].next) d[e[i].to]++; } return sum; } int main() { n=read();m=read(); bool flag=0; for(int i=1;i<=m;i++) { char ch[10]; scanf("%s",ch); if(ch[0]=='Q') { if(flag)puts("0"); else { int t=getans(); printf("%d\n",t); if(t==0)flag=1; } } else { int u=read(),v=read(); if(!flag)ins(u,v); } } return 0; } |
100分
|
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 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 |
#include<cstdio> #include<cmath> #include<ctime> #include<cstring> #include<iostream> #include<algorithm> #include<queue> #include<set> #define ll long long #define mod 1000000007 #define inf 1000000000 using namespace std; int read() { int f=1,x=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int n,m,cnt; struct E{ int to,next,v; }e[1000005]; struct G{ int hoop,hpsize,del; bool d3; int fa[100005],d[100005],last[100005],size[100005]; void ini(){ for(int i=1;i<=n;i++)fa[i]=i,size[i]=1; } void insert(int u,int v){ e[++cnt].to=v;e[cnt].next=last[u];last[u]=cnt; e[++cnt].to=u;e[cnt].next=last[v];last[v]=cnt; } int find(int x){ return x==fa[x]?x:fa[x]=find(fa[x]); } void add_edge(int u,int v){ if(u==del||v==del)return; d[u]++;d[v]++; insert(u,v); if(d[u]>=3||d[v]>=3)d3=true; int p=find(u),q=find(v); if(p==q) { hoop++;hpsize=size[q]; } else { fa[p]=q;size[q]+=size[p]; } } }g[5]; void Del(int p,int tmp) { g[tmp].ini(); g[tmp].del=p; for(int k=1;k<=n;k++) for(int i=g[0].last[k];i;i=e[i].next) if(e[i].to>k) g[tmp].add_edge(k,e[i].to); } void rebuild() { int p,tmp=0; for(int i=1;i<=n;i++)if(g[0].d[i]>=3)p=i; for(int i=g[0].last[p];i;i=e[i].next) Del(e[i].to,++tmp); Del(p,++tmp); } int getans() { if(g[0].hoop>1)return 0; else { if(g[0].d3==0) { if(!g[0].hoop)return n; else return g[0].hpsize; } else { int ans=0; for(int i=1;i<=4;i++) if(!g[i].hoop&&!g[i].d3)ans++; return ans; } } } int main() { n=read();m=read(); g[0].ini(); bool flag=0; char opt[5];int x,y; while(m--) { scanf("%s",opt+1); if(opt[1]=='Q') { if(flag)puts("0"); else { int t=getans(); if(t==0)flag=1; printf("%d\n",t); } } else { x=read();y=read(); if(flag)continue; if(g[0].d3==0) { g[0].add_edge(x,y); if(g[0].d3>=1)rebuild(); } else for(int i=1;i<=4;i++)g[i].add_edge(x,y); } } return 0; } |
Subscribe
计数器 9774031
OI 课件=>
OI 课件=>