并查集

自用笔记算法

并查集简单应用&简单搜索

hihocoder 1322

题目要求

判断给定的是否是一棵树

参考AC代码(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
#include<bits/stdc++.h>
#define maxn 550
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
vector<int>e[maxn];
int vis[maxn];
void dfs(int x){
	vis[x]=1;
	for(int i=0;i<e[x].size();i++){
		int next=e[x][i];
		if(!vis[next]) dfs(next);	
	}
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		for(int i=0;i<=n;i++) e[i].clear();
		mm(vis,0);
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			e[x].pb(y);
			e[y].pb(x);
		}
		dfs(1);
		int flag=1;
		for(int i=1;i<=n;i++){
			if(!vis[i]){
				flag=0;
				break;
			}
		} 
		if(flag && n==m+1) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

参考AC代码(并查集版)

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
#include<bits/stdc++.h>
#define maxn 505
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int p[maxn];
int find(int x){
	return p[x]==x?x:p[x]=find(p[x]);
}
void solve(int u,int v){
	int x=find(u);
	int y=find(v);
	if(x!=y) p[x]=y;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int t; cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) p[i]=i;
		for(int i=1;i<=m;i++){
			int x,y;
			cin>>x>>y;
			solve(x,y);
		}
		int count=0;
		for(int i=1;i<=n;i++){
			if(p[i]==i) count++;
			if(count>1) break;
		}
		if(count==1 && n==m+1) cout<<"YES"<<endl;
		else cout<<"NO"<<endl;
	}
	return 0;
}

思路

dfs版：从1点开始遍历 所有经过的点标记 如果所有的点都被标记且n==m+1 yes 否则no
并查集版：只有一个联通分量并且该连通分量里无环(n==m+1)

HDU 1232

题目要求

求加多少条边后图中的任意两点都有路径

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
using namespace std;
int p[maxn];
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void solve(int u,int v){
    int x=find(u);
    int y=find(v);
    if(x!=y) p[x]=y;
}
int main(){
//    freopen("input.txt","r",stdin);
    int n,m;
    while(scanf("%d",&n)&&n){
        scanf("%d",&m);
        for(int i=1;i<=n;i++) p[i]=i;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            solve(x,y);
        }        
        int count=0;
        for(int i=1;i<=n;i++){
            if(p[i]==i) count++;
        }
        printf("%d\n",count-1);
    }
    return 0;
}

思路

转换为：连通分量个数-1

HDU 1213

题目要求

求连通分量个数

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 1050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int p[maxn];
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void solve(int u,int v){
    int x=find(u);
    int y=find(v);
    if(x!=y) p[x]=y;
}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int t;
    cin>>t;
    while(t--){
        int n,m;
        cin>>n>>m;
        for(int i=1;i<=n;i++) p[i]=i;
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            solve(x,y);
        }
        int count=0;
        for(int i=1;i<=n;i++){
            if(p[i]==i) count++;
        }
        cout<<count<<endl;
    }
    return 0;
}

HDU 1272

题目要求

判断给定图是否为一棵树

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int p[maxn];
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void solve(int u,int v){
    int x=find(u);
    int y=find(v);
    if(x!=y) p[x]=y;
}
vector<int>e;
set<int>s;
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int x,y;
    while(cin>>x>>y){
        if(x==-1 && y==-1) break;
        if(x==0 && y==0){
            cout<<"Yes"<<endl;
            continue;
        }
        e.clear(),s.clear();
        int n=0,m=0;
        for(int i=1;i<maxn;i++) p[i]=i;
        while(x!=0 && y!=0){
            if(!s.count(x)) e.pb(x);
            if(!s.count(y)) e.pb(y);
            s.insert(x),s.insert(y);
            m++;
            solve(x,y);
            cin>>x>>y;
        }
        n=e.size();
        int count=0;
        for(int i=0;i<e.size();i++){
            int num=e[i];
            if(p[num]==num) count++;
            if(count>1) break;
        }
        if(count==1 && n==m+1) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

思路

注意本题中空树要输出yes
点也不是从0开始的 用set判重后加入vector确定顶点个数 也可用hash判断
之后和判树一样

HDU 1325

题目要求

判断有向图是否为树

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100000
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int hashh[maxn];
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int x,y;
	int f=1;
	while(cin>>x>>y){
		if(x<0 && y<0) break;
		if(x==0 && y==0){
			cout<<"Case "<<f++<<" is a tree."<<endl;
			continue;
		} 
		mm(hashh,0);
		int flag=0;
		int n=0,m=0;
		while(x!=0 && y!=0){
			if(hashh[x]==0) n++;
			if(hashh[y]==0) n++;
			m++;
			if(hashh[y]==2) flag=1;
			hashh[x]=1,hashh[y]=2; 
			cin>>x>>y;
		}
		int cnt=0;
		for(int i=1;i<maxn;i++){
			if(hashh[i]==0) continue;
			if(hashh[i]==1) cnt++;
		}
		if(cnt>1) flag=1;
		if(flag==0 && n==m+1) cout<<"Case "<<f++<<" is a tree."<<endl;
		else cout<<"Case "<<f++<<" is not a tree."<<endl;
	}
	return 0;
}

思路

跟上题类似 区别在于无向图变成了有向图
满足树需要三个条件：
1.无环 通过n==m+1判断
2.无入度大于1的点 通过hash判断 u->v 令u的hash值为1 v的hash值为2 hash为2的点不能再有入度
3.只有一个入度为0的点(只能有一个根) 通过计算hash值为1的点 大于1是森林不是树

HDU 1856

题目要求

求最大连通分量的顶点数

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 100050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int p[maxn],num[maxn];
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
int solve(int u,int v){
    int x=find(u);
    int y=find(v);
    if(x!=y){
        p[x]=y;
        num[y]+=num[x];
    }
}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int m;
    while(cin>>m){
        if(m==0){
            cout<<"1"<<endl;
            continue;
        }
        int n=0;
        for(int i=1;i<maxn;i++){
            p[i]=i;
            num[i]=1;
        }
        for(int i=1;i<=m;i++){
            int x,y;
            cin>>x>>y;
            n=max(n,max(x,y));
            solve(x,y);
        }
        int ans=0;
        for(int i=1;i<=n;i++){
            if(num[i]>ans) ans=num[i];
        }
        cout<<ans<<endl;
    }
    return 0;
}

思路

统计每个结点下的子结点个数 用dfs会爆栈 所以使用并查集
每次合并的时候还要合并num顶点数 最后统计num最大值的就是所求

HDU 1102

题目要求

在最小生成树上加一个限制条件：
给出一些边确定已在MST中 用剩下的边构成MST

参考AC代码(kruskal)

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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct edge{
    int u,v,w;
    edge(int u,int v,int w):u(u),v(v),w(w){}
    bool operator < (const edge& x) const{
        return w<x.w;
    }
};
int p[maxn];
int n,ans,q;
vector<edge>e;
int find(int x){
    return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int u,int v){
    int x=find(u);
    int y=find(v);
    if(x!=y) p[x]=y;
}
void kruskal(){
    sort(e.begin(),e.end());
    int m=e.size();
    for(int i=0;i<m;i++){
        int u=e[i].u,v=e[i].v;
        int x=find(u),y=find(v);
        if(x!=y){
            ans+=e[i].w;
            p[x]=y;
        }
    }
}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    while(cin>>n){
        e.clear();
        ans=0;
        for(int i=1;i<=n;i++) p[i]=i;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int x;
                cin>>x;
                if(j>i) e.pb(edge(i,j,x));
            }
        }
        cin>>q;
        for(int i=1;i<=q;i++){
            int u,v;
            cin>>u>>v;
            merge(u,v);
        }
        kruskal();
        cout<<ans<<endl;
    }
    return 0;
}

参考AC代码(prim)

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
#include<bits/stdc++.h>
#define maxn 105
#define inf 0x3f3f3f3f
using namespace std;
int g[maxn][maxn];
int lowcost[maxn];
int visit[maxn];
int n;     
int prime(){
    int Min,mincost=0,next;
    memset(visit,0,sizeof(visit));
    for(int i=1;i<=n;i++){
        lowcost[i]=g[1][i];
    }
    visit[1]=1;
    for(int i=1;i<n;i++){
        Min=inf;
        for(int j=1;j<=n;j++){
            if(!visit[j] && Min>lowcost[j]){
                Min=lowcost[j];
                next=j;
            }
        }
        mincost+=Min;
        visit[next]=1;
        for(int j=1;j<=n;j++){
            if(!visit[j] && lowcost[j]>g[next][j]){
                lowcost[j]=g[next][j];
            }
        }
    }
    return mincost;
}
int main(){
//    freopen("input.txt","r",stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);
    while(cin>>n){
        memset(g,inf,sizeof(g));
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                cin>>g[i][j];
            }
        }
        int q; cin>>q;
        while(q--){
            int u,v;
            cin>>u>>v;
            g[u][v]=g[v][u]=0;
        }
        int cost=prime();
        cout<<cost<<endl;    
    }
    return 0;
}

思路

kruskal：并查集的思想 把必须加入的边在跑kruskal之前写加入到并查集中
在加边的时候可以只加j>i的边
prim:在跑prim之前先把必须加入的边权设为0

HDU 1829

题目要求

问给定的图是否是二分图

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 2050
using namespace std;
vector<int>e[maxn];
bool flag;
int color[maxn];
bool DFS(int v,int c){   
    color[v]=c;  
    for(int i=0;i<e[v].size();i++){  
        if(color[e[v][i]]==c)  
            return false;  
        if(color[e[v][i]]==0&&!DFS(e[v][i],-c))  
            return false;  
    }  
    return true;  
}  
int f=1;
int main(){
//	freopen("input.txt","r",stdin);
	int t;
	cin>>t;
	while(t--){
		int n,m;
		cin>>n>>m;
		for(int i=1;i<=n;i++) e[i].clear();  
		flag=true;
		memset(color,0,sizeof(color));
		for(int i=1;i<=m;i++){
			int u,v;
			cin>>u>>v;
			e[u].push_back(v);
			e[v].push_back(u);
		}
		for(int i=1;i<=n&&flag;i++)
			if(color[i]==0)
				flag=DFS(i,1);
		cout<<"Scenario #"<<f++<<":"<<endl;
		if(flag)
			cout<<"No suspicious bugs found!"<<endl;
		else
			cout<<"Suspicious bugs found!"<<endl;
		cout<<endl;
	}
	return 0;
}

思路

dfs交叉染色模版

HDU 1598

题目要求

给出一些边和边权
多个询问 每次循环一个起点和终点 若无法到达输出-1
否则输出起点到终点的路径上最大权-最小权的最小值

参考AC代码(并查集)

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
#include<bits/stdc++.h>
#define maxn 205
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
int p[maxn];
struct node{
	int u,v,w;
	node(int u,int v,int w):u(u),v(v),w(w){}
	bool operator < (const node& x) const{
		return w<x.w;
	}
};
vector<node>e;
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int u,int v){
	int x=find(u);
	int y=find(v);
	if(x!=y) p[x]=y;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	while(cin>>n>>m){
		e.clear();
		for(int i=1;i<=m;i++){
			int u,v,w;
			cin>>u>>v>>w;
			e.pb(node(u,v,w));
		}
		sort(e.begin(),e.end());
		int q; cin>>q;
		while(q--){
			int s,t;
			cin>>s>>t;
			int Min=inf;
			for(int i=0;i<m;i++){
				for(int j=1;j<=n;j++) p[j]=j;
				for(int j=i;j<m;j++){
					merge(e[j].u,e[j].v);
					if(find(s)==find(t)){
						Min=min(Min,e[j].w-e[i].w);
						break;
					}
				}
			}
			if(Min==inf) cout<<"-1"<<endl;
			else cout<<Min<<endl;
		}
	}
	return 0;
}

参考AC代码(二分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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
#include<bits/stdc++.h>
#define maxn 205
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
struct edge{
	int to,w;
	edge(int to,int w):to(to),w(w){}
};
vector<edge>e[maxn];
vector<int>sp;
int vis[maxn];
void dfs(int s,int low,int up){
	vis[s]=1;
	int len=e[s].size();
	for(int i=0;i<len;i++){
		int speed=e[s][i].w,next=e[s][i].to;
		if(speed<=up && speed>=low && !vis[next])
		dfs(next,low,up);
	}
}
void solve(int s,int t){
	int l=0,r=1e9,mid,ans=inf;
	while(l<=r){
		mid=(l+r)>>1;
		int len=sp.size();
		int f=0;
		for(int i=0;i<len;i++){
			mm(vis,0);
			int speed=sp[i];
			dfs(s,speed,speed+mid);
			if(vis[t]){
				f=1;
				break;
			}
		}
		if(f){
			ans=mid;
			r=mid-1;
		}
		else l=mid+1;
	}
	if(ans==inf) cout<<"-1"<<endl;
	else cout<<ans<<endl;
}
int main(){
//	freopen("input.txt","r",stdin);
//	freopen("ouput.txt","w",sdout);
	ios::sync_with_stdio(false);
	cin.tie(0),cout.tie(0);
	int n,m;
	while(cin>>n>>m){
		for(int i=0;i<=n;i++) e[i].clear();
		sp.clear();
		while(m--){
			int u,v,w;
			cin>>u>>v>>w;
			e[u].pb(edge(v,w));
			e[v].pb(edge(u,w));
			sp.pb(w);
		}
		sort(sp.begin(),sp.end());
		int q; cin>>q;
		while(q--){
			int s,t;
			cin>>s>>t;
			solve(s,t);
		}
	}
	return 0;
}

思路

1.类似于MST的贪心 边权排序后从最小的开始遍历 寻找比它的大的边权 同时维护差值的最小值
对于每一个最小边 更新并查集 接着把新边加入到并查集中 如s和t在一个连通分量中 更新Min
2.二分差值 贪心枚举下界 上界=下界+差值 在这个上下界内能从s跑到t 说明这个差值满足题意 继续二分直到找到最小值
对比：两种方法对比后 第二种方法的时间优于第一种 在于第一种方法复杂度n² 暴力枚举最小边和最大边
第二种方法复杂度nlogn 暴力枚举下界二分差值 等于确定了上下界

HDU 1269

题目要求

判断一个有向图是否为强连通图(任意两点ij都有路径i->j j->i)

参考AC代码

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
#include<bits/stdc++.h>
#define maxn 10050
#define inf 0x3f3f3f3f
#define LL long long
#define pb push_back
#define pii pair<int,int>
#define fi first
#define se second
#define mm(a,b) memset(a,b,sizeof(a))
#define mp(a,b) make_pair(a,b)
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
const double eps = 1e-6;
const LL mod=1e9+7;
const LL INF=(LL)1e18;
using namespace std;
LL gcd(LL a,LL b){return b==0?a:gcd(b,a%b);}
LL qpow(LL x,LL y){LL re=1,base=x%mod;while(y){if(y&1)re=(re*base)%mod;base=(base*base)%mod;y>>=1;}return re;}
vector<int>e[maxn];
int vis[maxn];
void dfs(int x){
    vis[x]=1;
    int len=e[x].size();
    for(int i=0;i<len;i++){
        int next=e[x][i];
        if(!vis[next]) dfs(next);
    }
}
int main(){
//    freopen("input.txt","r",stdin);
//    freopen("ouput.txt","w",sdout);
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    int n,m;
    while(cin>>n>>m){
        if(n==0 && m==0) break;
        for(int i=0;i<=n;i++) e[i].clear();
        for(int i=1;i<=m;i++){
            int u,v;
            cin>>u>>v;
            e[u].pb(v);
        }
        int flag=1;
        for(int i=1;i<=n;i++){
            mm(vis,0);
            dfs(i);
            for(int i=1;i<=n;i++){
                if(!vis[i]){
                    flag=0;
                    break;
                }
            }
            if(flag==0) break;
        }
        if(flag) cout<<"Yes"<<endl;
        else cout<<"No"<<endl;
    }
    return 0;
}

思路

本题使用的dfs暴力 每个点dfs一遍 判断是否经过所有的点
Kosaraju和Tarjan算法将在后续的博客中提到

poj 1182

题目要求

动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B， B吃C，C吃A。
现有N个动物，以1－N编号。每个动物都是A,B,C中的一种，但是我们并不知道它到底是哪一种。
有人用两种说法对这N个动物所构成的食物链关系进行描述：
第一种说法是”1 X Y”，表示X和Y是同类。
第二种说法是”2 X Y”，表示X吃Y。
此人对N个动物，用上述两种说法，一句接一句地说出K句话，这K句话有的是真的，有的是假的。当一句话满足下列三条之一时，这句话就是假话，否则就是真话。
1） 当前的话与前面的某些真的话冲突，就是假话；
2） 当前的话中X或Y比N大，就是假话；
3） 当前的话表示X吃X，就是假话。
你的任务是根据给定的N（1 <= N <= 50,000）和K句话（0 <= K <= 100,000），输出假话的总数。

输入第一行是两个整数N和K，以一个空格分隔。
以下K行每行是三个正整数 D，X，Y，两数之间用一个空格隔开，其中D表示说法的种类。
若D=1，则表示X和Y是同类。
若D=2，则表示X吃Y。

输出只有一个整数，表示假话的数目。

参考AC代码

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
#include<cstdio>
#define maxn 50050
using namespace std;
int n,k;
int p[maxn*3];
int find(int x){
	return x==p[x]?x:p[x]=find(p[x]);
}
void merge(int x,int y){
	x=find(x),y=find(y);
	if(x!=y) p[x]=y;
}
bool same(int x,int y){
	return find(x)==find(y);
}
int main(){
//	freopen("input.txt","r",stdin);
	scanf("%d%d",&n,&k);
	for(int i=1;i<=3*n;i++) p[i]=i;
	int ans=0;
	while(k--){
		int op,x,y;
		scanf("%d%d%d",&op,&x,&y);
		if(x>n || y>n) ans++;
		else{
			if(op==1){
				if(same(x,y+n) || same(x,y+2*n)) ans++;
				else{
					merge(x,y);
					merge(x+n,y+n);
					merge(x+2*n,y+2*n);
				}
			}
			else{
				if(same(x,y) || same(x,y+2*n)) ans++;
				else{
					merge(x,y+n);
					merge(x+n,y+2*n);
					merge(x+2*n,y);
				}
			}
		}
	}
	printf("%d\n",ans);
	return 0;
}

思路

把n扩大三倍 相当于3个集合 1~n n~2n 2n~3n 分别用ABC表示
集合内部表示若same(x)==same(y) 表示x和y属于同一关系
same(x)==same(y+n)表示x吃y
same(x)==same(y+2n)表示y吃x
merge之前要先判断是否合法

本文标题:并查集

文章作者:Hippopmonkey

发布时间:2017-08-03, 11:22:21

最后更新:2018-04-30, 11:42:41

原始链接:http://xuboming8.github.io/2017/08/03/并查集/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. 并查集简单应用&简单搜索
    1. 1.1. hihocoder 1322
      1. 1.1.1. 题目要求
      2. 1.1.2. 参考AC代码(dfs版)
      3. 1.1.3. 参考AC代码(并查集版)
      4. 1.1.4. 思路
    2. 1.2. HDU 1232
      1. 1.2.1. 题目要求
      2. 1.2.2. 参考AC代码
      3. 1.2.3. 思路
    3. 1.3. HDU 1213
      1. 1.3.1. 题目要求
      2. 1.3.2. 参考AC代码
    4. 1.4. HDU 1272
      1. 1.4.1. 题目要求
      2. 1.4.2. 参考AC代码
      3. 1.4.3. 思路
    5. 1.5. HDU 1325
      1. 1.5.1. 题目要求
      2. 1.5.2. 参考AC代码
      3. 1.5.3. 思路
    6. 1.6. HDU 1856
      1. 1.6.1. 题目要求
      2. 1.6.2. 参考AC代码
      3. 1.6.3. 思路
    7. 1.7. HDU 1102
      1. 1.7.1. 题目要求
      2. 1.7.2. 参考AC代码(kruskal)
      3. 1.7.3. 参考AC代码(prim)
      4. 1.7.4. 思路
    8. 1.8. HDU 1829
      1. 1.8.1. 题目要求
      2. 1.8.2. 参考AC代码
      3. 1.8.3. 思路
    9. 1.9. HDU 1598
      1. 1.9.1. 题目要求
      2. 1.9.2. 参考AC代码(并查集)
      3. 1.9.3. 参考AC代码(二分dfs)
      4. 1.9.4. 思路
    10. 1.10. HDU 1269
      1. 1.10.1. 题目要求
      2. 1.10.2. 参考AC代码
      3. 1.10.3. 思路
    11. 1.11. poj 1182
      1. 1.11.1. 题目要求
      2. 1.11.2. 参考AC代码
      3. 1.11.3. 思路
|