首页 > 代码库 > 第48套题【tarjan】【图&树的连通性】【并查集】
第48套题【tarjan】【图&树的连通性】【并查集】
Problem 1 图的连通性
??题目背景??
琼和雪不知从什么时候就开始形影不离得呆在一起，无话不说了
那天她们在谈论图论
??题意描述??
“有一个无向图，每次断掉一条边，并询问两个点时候联通，你会维护么？
” 琼很认真地问。
“为什么要知道这个呢？”
“我们总要知道自己是否身陷囹囵……你必须立刻告诉我答案哦”
??输入格式??
测试数据的第一行是三个正整数n、m、t, 表示无向图有n 个点，m 条边
和t 个操作
接下来m 行，每行两个正整数x、y，表示x 和y 之间有一条边（允许存
在重边）
接下来t 行，每行三个整数w x y，w=1 时表示将x 和y 之间的边剪断
（保证存在这样一条边）。w=2 时表示查询x 与y 时候联通，是输出1, 否则输
出0。
为了保证强制在线，最后t 行输入数据中的x 和y 必须要??或（C/C++ 中的^ ??
算，PASCAL 中的xor）执行当??操作之??图中????的边数，??能得到实际问题中的
x 和y
??输出格式??
对于每次询问，输出一行，一个数，1 或0，1 表示联通，0 表示不联通。
??样例输入??
5 9 6
1 2
2 3
1 3
1 3
3 1
1 5
1 4
3 5
5 4
1 12 13
2 13 12
1 9 12
2 3 2
1 4 6
2 7 5
??样例输出??
1
0
1
??样例说明??
6 个操作依次为：
1. 断掉5 和4 之间的边
2. 查询5 和4 之间的连通性
3. 断掉1 和4 之间的边
4. 查询5 和4 之间的连通性
5. 断掉1 和3 之间的边
6. 查询1 和3 之间的连通性
??数据规模和约定??
对于40% 的数据，n <=100; m <= 1000; t <= 500
对于100% 的数据，n <= 100000; m <= 150000; t <=100000
Problem 2 树的连通性
??题目背景??
雪的眉头紧缩
“是不是那个问题太困难了？” 琼问到。
雪点了点头
“那好，我们简化一下问题，假设图保证联通，没有重边，也没有环，重复
刚刚的问题，是不是简单一些？”
雪的眼中冒着希望的光芒
“你还是要立刻告诉我答案哦。” 琼笑了
??题意说明??
给定一个n 个点的无向图，保证联通且无环无重边，每个点上有一个可修
改的权值，每次断掉一条边、修改某个节点上的权值或询问两个点之间的连通
性。
??输入格式??
输入数据的第一行是两个数N、M，点的个数和操作的个数
接下来N 行，每行一个正整数，表示每个点上的初始权值
接下来若干行，每行两个数x 和y，表示x 和y 之间有一条无向边
接下来M 行，每行三个数t x y，含义如下：
t=1 将x 和y 之间的边断开（保证存在）
t=2 查询x 和y 是否联通，若联通，输出他们权值的乘积，否则输出他
们权值的和
t=3 将点x 上的权值修改为y
为了保证算法强制在线，设上一次查询的结果为lastans，则最后t 行输入
数据的x 和y 的实际值= 输入值xor lastans, lastans 的初始值为0
??输出格式??
对于每个查询操作，输出一行一个数，要求如上所示
??样例输入??
8 5
1
2
3
4
5
6
7
8
1 2
1 5
4 2
3 2
5 7
5 6
8 5
1 5 1
2 4 6
2 11 9
3 0 15
2 0 11
??样例输出??
10
3
20
??样例说明??
先断开1 和5 之间的边，然后查询4 和6 的连通性。由于不联通，所以答
案是10
然后查询1 和3 的连通性，由于联通，所以答案是3
然后将3 号节点上的数值修改为12
最后查询3 和8 的连通性。由于不联通，所以答案是它们的权值和20
??数据规模和约定??
对于10% 的数据，没有断边操作
对于40% 的数据，n 1000; m 500
对于100% 的数据，n 200000; m 200000，0 < 点上的权值 1000
Problem 3 逻辑的连通性
??题目背景??
“我已经快疯了，是时候整理一下心中的逻辑了。” 雪说着，打开了《高中
数学·选修2-1》
??题意说明??
假如有命题p 一定能推出命题q，则称p 是q 的充分条件，q 是p 的必要
条件。
特别的，当p 既是q 的充分条件，又是q 的必要条件时，称p 和q 互为
充要条件
现在有n 个命题，其中一些是另一些的充分条件。请问有多少对命题互为
充要条件？
??输入格式??
第一行三个正整数n，m，t，分别表示命题数、已知关系数和询问数
接下来m 行，每行两个正整数p 和q，表示命题p 是命题q 的充分条件
??输出格式??
仅一行，一个整数，表示充要条件的对数
??样例输入??
5 5
1 3
3 2
2 1
4 5
5 4
??样例输出??
4
??样例说明??
4 对充要条件分别是（1, 2）、（2, 3）、（1, 3）、（4, 5）
??数据规模和约定??
对于10% 的数据，n <=10;m <=50
对于40% 的数据，n <= 500;m <= 1000
对于另外10% 的数据，数据中保证没有重边且m = n^2
对于100% 的数据，n <=50000;m <=600000
解题报告：参考题解：http://blog.csdn.net/ourfutr2330/article/details/52744358
第一题：考试的时候乱写的暴力，还顺便复制给第二题用，结果无向边又忘开两倍了。。于是崩了。正解：其实不是强制在线，可以先把所有要删的边都删了，然后再一条一条的加上去，用并查集的思想，合并，查询的时候用find()就对了。注意：输出的时候答案一定要倒序输出，因为是倒着处理的每个操作；
删边：
void cut(int a,int b)//删边 { int v=he[a]; if (to[v]==b) {//在第一条边 he[a]=ne[v]; //v=ne[v]; } else while (ne[v]){//在中间 if (to[ne[v]]==b) {// 不是 to[v]，因为要跳过第一条边 ne[v]=ne[ne[v]]; return ; } v=ne[v]; }}
然后并查集的一些基本操作再复习一下：
void unionn(int u,int v)//合并 { fa[v]=u; } { int r1=find(x); int r2=find(y) ; if (r1!=r2) unionn(r1,r2);//注意合并的是r1，r2 ，不是x，y }
1 int find(int u)2 {3 if (fa[u]!=u) return fa[u]=find(fa[u]);//全部改他们的 fa 4 return fa[u];5 }
代码：
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define maxn 100005 6 #define inf 300005 7 using namespace std; 8 int m,n,t,delt,fa[maxn],ans[maxn],hh; 9 int tot,ne[inf],he[maxn],to[inf]; 10 bool vis[maxn]; 11 struct pp{ 12 int ti,x,y; 13 }; 14 pp qus[maxn]; 15 void add(int a,int b) 16 { 17 tot++;ne[tot]=he[a];to[tot]=b;he[a]=tot; 18 } 19 int find(int u) 20 { 21 if (fa[u]!=u) return fa[u]=find(fa[u]);//全部改他们的 fa 22 return fa[u]; 23 } 24 void unionn(int u,int v) 25 { 26 fa[v]=u; 27 } 28 void cut(int a,int b)//删边 29 { 30 int v=he[a]; 31 if (to[v]==b) { 32 he[a]=ne[v]; 33 //v=ne[v]; 34 } 35 else while (ne[v]){ 36 if (to[ne[v]]==b) {//ne[v] 37 ne[v]=ne[ne[v]]; 38 return ; 39 } 40 v=ne[v]; 41 } 42 } 43 int main() 44 { 45 freopen("graph.in","r",stdin); 46 //freopen("graph.out","w",stdout); 47 cin>>n>>m>>t; 48 for (int i=1;i<=m;i++) 49 { 50 int a,b; 51 scanf("%d%d",&a,&b); 52 add(a,b); 53 add(b,a); 54 } 55 delt=m; 56 for (int i=1;i<=t;i++) 57 { 58 int tt=i; 59 scanf("%d%d%d",&qus[tt].ti,&qus[tt].x,&qus[tt].y); 60 if (qus[tt].ti==1) { 61 qus[tt].x^=delt;qus[tt].y^=delt; 62 cut(qus[tt].x,qus[tt].y); 63 cut(qus[tt].y,qus[tt].x);//先全部删掉 64 delt--; 65 } 66 else { 67 qus[tt].x^=delt;qus[tt].y^=delt; 68 } 69 } 70 for (int i=1;i<=n;i++) 71 fa[i]=i; 72 for (int i=1;i<=n;i++) 73 { 74 int v=he[i]; 75 while (v) 76 { 77 if (find(i)!=find(to[v])) 78 { 79 unionn(fa[i],fa[to[v]]);//修改fa的fa而不是当前点的fa 80 } 81 v=ne[v]; 82 } 83 } 84 for (int i=t;i>=1;i--) 85 { 86 int vi,vj; 87 vi=find(qus[i].x); 88 vj=find(qus[i].y); 89 if (qus[i].ti==1) { 90 //add(qus[i].x,qus[i].y);add(qus[i].y,qus[i].x); 91 if (vi!=vj) unionn(vi,vj);//修改find(x)不是 x 92 } 93 else{ 94 hh++; 95 if (vi==vj) 96 ans[hh]=1; 97 } 98 } 99 for(int i=hh;i>=1;i--)100 {101 printf("%d\n",ans[i]);//倒序输出答案 102 }103 return 0;104 }
第二题：
利用它是一棵树的性质，可以修改是另一个点的儿子的点，将它的下面的所有儿子点修改一个值 f[i] ，这样可以保证每个不连通的点的 f 值都不一样，查询的时候判断一下 f 数组就可以了。但是一定要注意，删掉这条边还是必要的，因为会对下面的询问有影响，不删的话，修改的时候就会多修改一些点。
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<queue> 5 #define maxn 200005 6 using namespace std; 7 int n,t,lastans,va[maxn],f[maxn],cnt,fa[maxn]; 8 int tot,ne[maxn*2],he[maxn],to[maxn*2]; 9 void add(int a,int b)10 {11 tot++;ne[tot]=he[a];to[tot]=b;he[a]=tot;12 }13 void dfs(int x)14 {15 int u=he[x];16 f[x]=cnt;17 while (u)18 {19 if (to[u]!=fa[x])//向下建树 20 {21 fa[to[u]]=x;22 dfs(to[u]);23 }24 u=ne[u];25 }26 }27 void cut(int a,int b)28 {29 int v=he[a];30 while (to[v]==b)//要删的边在head开头 31 {32 he[a]=ne[v];33 v=ne[v];34 return ;35 }36 while (ne[v])//要删的边在中间 37 {38 if (to[ne[v]]==b)39 {40 ne[v]=ne[ne[v]];41 return ; 42 }43 v=ne[v];44 }45 }46 int main()47 {48 freopen("tree.in","r",stdin);49 freopen("tree.out","w",stdout);50 cin>>n>>t;51 for (int i=1;i<=n;i++)52 scanf("%d",&va[i]);53 for (int i=1;i<=n-1;i++)54 {55 int a,b;56 scanf("%d%d",&a,&b);57 add(a,b);58 add(b,a);59 }60 dfs(1);61 for (int i=1;i<=t;i++)62 {63 int x,y,z;64 scanf("%d%d%d",&z,&x,&y);65 x=(lastans^x); y=(y^lastans);66 if (z==1) {67 cut(x,y);68 cut(y,x);69 cnt++;70 if (x==fa[y]) dfs(y);71 else dfs(x);72 }73 else if (z==2){74 if (f[x]==f[y]) lastans=va[x]*va[y];75 else lastans=va[x]+va[y];76 cout<<lastans<<endl;77 }78 else if (z==3){79 va[x]=y;80 }81 }82 return 0;83 }
第三题：
一秒 tarjan 。还是要多复习啊。只不过我的tarjan怎么这么慢。。。
1 #include<iostream> 2 #include<cstdio> 3 #include<map> 4 #include<cstring> 5 #define maxn 50005 6 #define inf 600005 7 #define ll long long 8 using namespace std; 9 int n,m,s[maxn],dfn[maxn],low[maxn],init,num;10 int tot,he[maxn],ne[inf],to[inf];11 ll ans;12 bool vis[maxn],in[maxn];13 void add(int a,int b)14 {15 tot++;ne[tot]=he[a];to[tot]=b;he[a]=tot;16 }17 void tarjan(int x)18 {19 dfn[x]=low[x]=++num;20 s[++init]=x;21 in[x]=true;22 for (int i=he[x];i;i=ne[i])23 if (!vis[to[i]]){24 if (!dfn[to[i]]){25 tarjan(to[i]);26 if (low[to[i]]<low[x]) 27 low[x]=low[to[i]];28 }29 if (in[to[i]]&&low[x]>dfn[to[i]]) 30 low[x]=dfn[to[i]];31 }32 int u;33 ll p=0;34 if (dfn[x]==low[x]) {35 do36 {37 u=s[init--];38 in[u]=false;39 vis[u]=true;40 p++;41 }while (u!=x);42 ans+=p*(p-1)/2;43 }44 }45 int main()46 {47 freopen("logic.in","r",stdin);48 freopen("logic.out","w",stdout);49 cin>>n>>m;50 for (int i=1;i<=m;i++)51 {52 int x,y;53 scanf("%d%d",&x,&y);54 add(x,y);55 }56 for (int i=1;i<=n;i++)57 if (!vis[i]) {58 memset(in,0,sizeof (in));59 memset(s,0,sizeof (s));60 memset(dfn,0,sizeof (dfn));61 memset(low,0,sizeof (low));62 tarjan(i); 63 }64 cout<<ans;65 return 0;66 }
国庆要完了，我在学校里面都三天了。。作业还没做完。。今天开夜车哇。
第48套题【tarjan】【图&树的连通性】【并查集】