畅通工程

#include<iostream>
(720)#include<cstdio>

using namespace std;

const int MaxN = 1000;

int father[MaxN];
int height[MaxN];

void Initial(int n){
    for(int i=1; i<=n; i++){
        father[i] = i;
        height[i] = 0;
    }
}

int Find(int x){
    if(x!=father[x]){
        father[x] = Find(father[x]);
    }
    return father[x];
}

void Union(int x,int y){
    x = Find(x);
    y = Find(y);
    if(x!=y){
        if(height[x]>height[y]){
            father[y] = x;
        }
        else if(height[x]<height[y]){
            father[x] = y;
        }
        else{
            father[y] = x;
            height[x]++;
        }
    }
    return;
}

int main(){
    int N,M;
    while(cin>>N){
        if(N==0){
            break;
        }
        cin>>M;
        Initial(N);
        for(int i=0; i<M; i++){
            int a,b;
            cin>>a>>b;
            Union(a,b);
        }
        int answer = -1;
        for(int i=1; i<=N; i++){
            if(i==Find(i)){
                answer++;
            }
        }
        cout<<answer<<endl;
    }
    return 0;
}

//并查集
//求连通分量数

#include<iostream>

using namespace std;

const int MAX_N = 1001;

int father[MAX_N];
int height[MAX_N];

void Init(int n){
    // 各结点的父结点初始为自己
    // 求连通分量数，即求父结点是自己的结点个数
    for(int i = 0; i <= n; i++){
        father[i] = i;
        height[i] = 0;
    }
}

// 查，查找父结点
int Find(int x){
    // 路径压缩，直接链接到根结点下，使树尽可能矮
    if(x != father[x]){
        father[x] = Find(father[x]);
    }
    return father[x];
}

// 并
void Union(int a, int b){
    // 查找两个结点的根节点
    a = Find(a);
    b = Find(b);
    
    // 根节点不同，进行合并
    if(a != b){
        // 合并时，把矮的合并到高的，树高不变
        if(height[a] < height[b]){
            father[a] = b;
        }
        else if(height[a] > height[b]){
            father[b] = a;
        }
        else{
            father[a] = b;
            height[b]++;
        }
    }
}

int main(){
    // n 表示城镇数， m 表示道路数
    int n, m;
    while(cin >> n){
        if(n == 0)
            break;
        cin >> m;
        // 初始化
        Init(n);
        // 输入道路
        while(m--){
            int x, y;
            cin >> x >> y;
            Union(x, y);
        }
        // 经过合并后，连通分量数=父结点是自己的结点数
        // 要修建的道路数 = 连通分量数 - 1
        // ans 初始为 -1，不是 0
        int ans = -1;
        for(int i = 1; i <= n; i++){
            if(father[i] == i){
                ans++;
            }
        }
        cout << ans << endl;
    }
    return 0;
}

#include<iostream>
using namespace std;

const int maxn = 1000;
int father[maxn];
int height[maxn];

void Initial(int n)
{
	for (int i = 0; i <= n; i++)
	{
		father[i] = i;
		height[i] = 0;
	}
}
int Find(int x)
{
	if (x != father[x])//当元素不是集合根部时
		father[x] = Find(father[x]);//路劲压缩，直接指向根节点，使树高最小
	return father[x];
}
void Union(int x, int y)
{
	x = Find(x);//先找到集合根部
	y = Find(y);
	if (x != y)//不是同一个集合根部，即不是同一个集合
	{//矮树往高树合并,提高查询效率
		if (height[x] < height[y])
			father[x] = y;
		else if (height[x] > height[y])
			father[y] = x;
		else//一样高
		{
			father[y] = x;
			height[x]++;
		}
	}
}
int main()
{
	int N, M;
	while (cin>>N && N != 0 && cin>>M)
	{
		Initial(N);
		while (M--)
		{
			int x, y;
			cin >> x >> y;
			Union(x, y);
		}
		int ans = -1;//N个城镇最少N-1条路就能连通了
		for (int i = 1; i <= N; i++)
			if (Find(i) == i)//检查集合数量，即没连通的城镇数量
				ans++;
		cout << ans << endl;
	}
	return 0;
}

#include<iostream>
(720)#include<bits/stdc++.h>
#define max 1000
using namespace std;

int father[max];
int length[max];

int find(int x){			//找节点x的根节点（如果是单个节点，就返回自己） 
	while(father[x]!=-1){
		x=father[x];
	}
	return x;
}


//思想是节点x和y联通，只需要将他们的根节点相连，也相当于他们连通 
void union_node(int x,int y){//此函数的目的是将x和y所在的树进行合并，并尽量使高度最小，减少find函数的查找次数 
	x = find(x);			
	y = find(y);
	if(x!=y){				//如果x和y节点的根节点相同，说明他们在同一条链中，不操作。 
		if(length[x]==length[y]){	//高度如果相等，选取任意一根节点作为另一节点的父节点 
			father[x]=y;
			length[y]++;			//被选取的根节点高度加1 
		}else{						
			length[x]>length[y]?father[y]=x:father[x]=y;//不相等，选取高度大的作为父节点 
		}
	}
	
}
int main(){
	int N,M,x,y;
	while(cin>>N&&N!=0){
		cin>>M;
		memset(father,-1,sizeof(father));
		memset(length,0,sizeof(length));
		while(M--){
			cin>>x>>y;
			union_node(x,y);
		}
		int ans=-1;					//父节点为1的节点有树的根节点和不连通的单个节点，所以设为-1去除根节点 
		for(int i=1;i<=N;i++){
			if(father[i]==-1) ans++;
		}
		cout<<ans<<endl;
	}
	return 0;
}

#include <iostream>
#include <cstring>
using namespace std;
#include <algorithm>
#define N 1001

int finds(int p[],int x){
    while(p[x]>0){
        x = p[x];
    }
    return x;
}

int main(){
    int n,m; ///n个城 m条路
    int p[N];
    int i,a,b;
    while(cin >> n >> m){
        if(n==0) break;
        memset(p,0,sizeof(p));
        for(i=0;i<m;++i){
            cin >> a >> b;
            int x = finds(p,a);
            int y = finds(p,b);
            if(x!=y){
                p[x] = y;
            }
        }
        int ans = -1;
        for(i=1;i<=n;i++){
            if(p[i]==0){
                ++ans;///找多少个非连通分量
            }
        }
        cout << ans << endl;
    }
    return 0;
}

while True:
    try:
        def findRoot(b):    #找树根
            global roads
            if roads[b] == 0:                #树根为0表示自己为根
                return b
            else:
                temp = findRoot(roads[b])
                roads[b] = temp
                return temp
        town,roadNum = list(map(int,input().split()))
        roads = [0 for i in range(town+1)]   #一开始每个树根为0,0下标我没用
        for i in range(roadNum):
            tempInput = list(map(int, input().split()))
            a = findRoot(tempInput[0])       #找出两个新来边的结点的根是否相同
            b = findRoot(tempInput[1])
            if a != b:                       #如果根不一样，这条路把他们连接到一起，两棵树缩成一棵树
                roads[a] = b
        print(roads.count(0)-2)   #0的数量减去1（下标为0的值为0）得到树的棵数，再减一得到需要造的路
    except Exception:
        break

import java.util.Scanner;
public class Main{
    static int[] parent;
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int N = in.nextInt();
            int M = in.nextInt();
            if(N==0)
                break;
            parent = new int[N+1];
            for(int i=0;i<=N;i++)
                parent[i]=-1;
            for(int i=0;i<M;i++){
                int left = in.nextInt();
                int right = in.nextInt();
                int leftParent = findroot(left);
                int rightParent = findroot(right);
                if(leftParent!=rightParent)
                    parent[rightParent] = leftParent;
                
            }
            int ans = 0;
            for(int i=1;i<=N;i++){
                if(parent[i]==-1)
                    ans++;
            }
            System.out.println(ans-1);
        }
    }
    public static int findroot(int index){
        if(parent[index]==-1)
            return index;
        int tmp = findroot(parent[index]);
        parent[index] = tmp;
        return tmp;
    }
}

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int find(const vector<bool> & v) {
    for(int i = 0; i<v.size(); i++) {
        if(v[i] == false) {
            return i;
        }
    }
    return -1;
}
 
int main() {
    //freopen("t.txt", "r", stdin);
 
    int N;
    while(cin>>N, N) {
        int M;
        cin>>M;
        vector<vector<bool>> mat(N, vector<bool>(N));
        for(int i = 0; i<M; i++) {
            int a, b;
            cin>>a>>b;
            a--,b--;
            mat[a][b] = true;
            mat[b][a] = true;
        }
 
        vector<bool> traversed(N, false);
        int start = 0;
        int res = -1;
        do {
            res++;
            queue<int> q;
            q.push(start);
            traversed[start] = true;
            while(!q.empty()) {
                int f = q.front(); q.pop();
                for(int link = 0; link < N; link++) {
                    if(f == link) continue;
                    if(mat[f][link] && traversed[link]==false) {
                        q.push(link);
                        traversed[link] = true;
                    }
                }
            }
        } while((start=find(traversed)) != -1);
        cout<<res<<endl;
    }
}

#include<iostream>
using namespace std;
int FindRoot(int a,int Tree[]){
    if(Tree[a]==-1) return a;
    else{
        int tmp=FindRoot(Tree[a],Tree);
        Tree[a]=tmp;
        return tmp;
    }
}
int main(){
    int n,m;
    int Tree[1001];
    while(cin>>n>>m&&n!=0){
        int a,b;
        for(int i=1;i<=n;i++)
            Tree[i]=-1;
        for(int i=0;i<m;i++){
            cin>>a>>b;
            a=FindRoot(a,Tree);
            b=FindRoot(b,Tree);
            if(a!=b)
                Tree[b]=a;
        }
        int ans=0;
        for(int i=1;i<=n;i++)
            if(Tree[i]==-1) ans++;
        cout<<ans-1<<endl;
    }
    return 0;
} 

#include <stdio.h>
#define N 1000

int parent[N];//parent[i]表示节点i的双亲是谁, -1表示不存在

int FindRoot(int x)//寻找x所在的树的根节点
{
    if(parent[x]==-1) return x;
    else//递归调用
    {
        int ret=FindRoot(parent[x]);
        parent[x]=ret;//路径压缩
        return ret;
    }
}

int main()
{
    int m, n;
    while(scanf("%d", &n)!=EOF)
    {
        if(n<=0) break;
        scanf("%d", &m);
        for(int i=1; i<=n; i++) parent[i]=-1;//一开始全是根
        while(m--)
        {
            int x, y;
            scanf("%d %d", &x, &y);
            x=FindRoot(x);
            y=FindRoot(y);
            if(x!=y) parent[y]=x;//不在同一棵树那就合并
        }
        int count=0;//统计一下根节点数量
        for(int i=1; i<=n; i++)
        {
            if(parent[i]==-1) count++;
        }
        printf("%d\n", count-1);
    }
    return 0;
}

//老哥们一看就是用的并查集
//我换种解法：dfs
#include<iostream>
using namespace std;
const int maxn=1001,INF=1000000000;
int n,m,g[maxn][maxn],d[maxn],vis[maxn];
void dfs(int s)
{
    vis[s]=1;
    for(int i=1;i<=n;i++)
    {
        if(vis[i]==0&&g[s][i]!=INF)
            dfs(i);
    }
}
int main()
{
    int a,b,ans;
    while(cin>>n&&n)
    {
        cin>>m;
        ans=0;
        fill(vis,vis+maxn,0);
        fill(g[0],g[0]+maxn*maxn,INF);
        for(int i=0;i<m;i++)
        {
            cin>>a>>b;
            g[a][b]=g[b][a]=1;
        }
        for(int i=1;i<=n;i++)
        {
            if(vis[i]==0)
            {
                ans++;
                dfs(i);
            }
        }
        cout<<ans-1<<endl;
    }
    return 0;
}

#include <stdio.h>
#include <string.h>

int father[1000];
int height[1000];

// Add proper parameter types in function declarations
void intial(int n) {
    for(int i = 0; i < n; i++) {
        father[i] = i;
        height[i] = 0;
    }
}

int Find(int n) {
    if(n != father[n]) {
        father[n] = Find(father[n]);
    }
    return father[n];
}

void Uion(int a, int b) {
    a = Find(a);
    b = Find(b);
    if (a != b) {
        if (height[a] > height[b]) {
            father[b] = a;  // Fix assignment
        }
        else if (height[a] < height[b]) {
            father[a] = b;  // Fix assignment
        }
        else {
            father[a] = b;
            height[b]++;
        }
    }
}

int main() {
    int a, b, c, d;
    while(scanf("%d %d", &a, &b) != EOF) {
        if (a == 0){
            break;
        }
        int ans = -1;
        intial(a);
        for(int i = 0; i < b; i++) {
            scanf("%d %d", &c, &d);
            Uion(c, d);
        }
        for(int i = 0; i < a; i++) {  // Change b to a
            if(i == father[i])
                ans++;
        }
        printf("%d\n", ans);  // Add output statement
    }
    return 0;
}

#include <iostream>
using namespace std;
int village[1010];
void Initset(int n){
    for(int i=0;i<n;i++){
        village[i]=i;
    }
}
int findfather(int n) {
    if (village[n] == n) {
        return n;
    } else return findfather(village[n]);
}
int main() {
    int n,m;
    int start,end;
    while (cin>>n>>m) { // 注意 while 处理多个 case
        if(n==0){
            break;
        }
        Initset(n+1);
        int setnode=n;
        for(int i=0;i<m;i++){
            cin>>start>>end;
            int startroot=findfather(start);
            int endroot=findfather(end);
            if(startroot!=endroot){
                setnode--;
                village[endroot]=startroot;
            }
        }
        cout<<setnode-1<<endl;
    }
    return 0;
}

#include <bits/stdc++.h>
using namespace std;

int fa[1005];
int find(int x) {
    return fa[x] == x ? x : fa[x] = find(fa[x]);
}
void merge(int x, int y) {
    x = find(x);
    y = find(y); 
    if(x<y) swap(x,y);
    fa[x] = y;
}
int main() {
    int n, m;
    while (cin >> n >> m) {
        for (int i = 1; i <= n; i++)
            fa[i] = i;
        while (m--) {
            int a, b;
            cin >> a >> b;
            merge(a, b);
        }
        int cnt = -1;
        for(int i=1;i<=n;i++)
        if(find(i)==i) cnt++;
        cout<<cnt;

    }
输出并查集数-1