C++ 并查集算法详解及代码示例

#include using namespace std; int f[105]; // 定义一个数组f，用来存储每个节点的父节点

void init(int n){ for(int i=1;i<=n;i++){ f[i]=i; // 初始化每个节点的父节点为自身 } }

int find(int x){ if(f[x]==x){ // 如果节点的父节点是自身，说明该节点为根节点 return x; } f[x]=find(f[x]); // 路径压缩，将节点的父节点直接指向根节点 return f[x]; }

void merge(int x,int y){ int a=find(x); // 找到x节点的根节点 int b=find(y); // 找到y节点的根节点 if(a!=b){ // 如果两个节点的根节点不同，说明它们不在同一个集合中 f[a]=f[b]; // 将两个集合合并，即将x节点的根节点指向y节点的根节点 } }

int main(){ int n,m,k; while(scanf("%d %d %d",&n,&m,&k)!=EOF){ init(n); // 初始化节点数组 int mp[n+5][n+5]; // 定义一个邻接矩阵，用来存储节点之间的关系 int a,b,c,d; for(int i=0;i<n+5;i++){ for(int j=0;j<n+5;j++){ mp[i][j]=0; // 初始化邻接矩阵 } } for(int i=0;i<m;i++){ cin>>a>>b>>c; // 输入两个节点和它们之间的关系 mp[a][b]=c; // 将节点a和节点b之间的关系存入邻接矩阵 mp[b][a]=c; // 将节点b和节点a之间的关系存入邻接矩阵 if(c==1){ // 如果节点a和节点b之间有直接关系（c=1） if(find(a)!=find(b)){ // 如果节点a和节点b不在同一个集合中 merge(a,b); // 将节点a和节点b所在的集合合并 } } } for(int i=0;i<k;i++){ cin>>a>>b; // 输入两个节点 if(mp[a][b]==1){ // 如果节点a和节点b之间有直接关系 cout<<"No problem"<<endl; // 输出"No problem" } else if(mp[a][b]==0){ // 如果节点a和节点b之间没有关系 cout<<"OK"<<endl; // 输出"OK" } else if(mp[a][b]==-1){ // 如果节点a和节点b之间的关系不确定 int f=0; // 定义一个标志位f if(find(a)==find(b)){ // 如果节点a和节点b在同一个集合中 cout<<"OK but..."<<endl; // 输出"OK but..." } else{ cout<<"No way"<<endl; // 输出"No way" } }

	}
}
return 0;