Find Function Optimization:
After Path compression：
int find(int x){
return root[x] == x ? x : (root[x] = find(root[x]));
}
Avoid Stack overflow:
int find(int a){
while(root[a]!=a){
a=root[a];
}
return a;
}
Combined with rank : (Combined with the height of tree)
int rank[MAXSIZE];
void UNION(int x, int y) {
int f1 = find(x);
int f2 = find(y);
if (rank[f1] <= rank[f2]) {
root[f1] = f2;
if (rank[f1] == rank[f2]) {
rank[f2] ++;
}
}
else root[f2] = f1;
}
Union Function :
void Union(int a,int b){
int ra = find(a);
int rb = find(b);
root[rb]=ra; // ra is the father of rb
}
Species Union - Find Function:
int find(int i){
if(root[i]==i)return i;
int ans=root[i];
root[i]=find(root[i]);
dis[i]+=dis[ans];//求出节点a到根的距离
return root[i];
}
void Union(int u,int v,int root_u,int root_v,int x){
root[root_v]=root_u;
dis[root_v]=dis[u]+x-dis[v];//使用的是数学中向量计算
}
while(m--){
scanf("%d%d%d",&u,&v,&dist);
int x=find(u),y=find(v);
if(x!=y)
Union(u,v,x,y,dist);
else
if(dis[u]+dist!=dis[v])
ans++;
}
Operation of Adjacency list :
int head[MAXSIZE];
struct node{
int cur,pre,weight;
}edge[MAXSIZE];
int cnt;//The num of Edges void initEdge(){
cnt = ;
for(int i = ; i< MAXSIZE; i++)
head[i] = -;
} void addEdge(int from , int cur){
edge[cnt].cur = cur;
edge[cnt].pre = head[from];
head[from] = cnt++;
} void print(int v){
for(int i = head[v]; i != -; i = edge[i].pre){
int cur = edge[i].cur;
printf("%d ",cur);
}
}
Topological sorting：
//按如下建图，A在B前，则建一条A->B的有向边
//按如下策略排序：
//图中每次删除入度为0的节点，删除的节点加入已排序序列末尾
int sortlist[];
int topsort(){
queue<int>q;
int idx = ;
for(int i = ; i < n; i++)//n为要排序的节点个数
if(indgree[i] == )
q.push(i);
while(!q.empty()){
int cur = q.front;
sortlist[idx++] = cur;
q.pop();
n--;
for(int i = ; i< l[cur].size(); i++){//l[cur][i]表示以cur为起点i为终点的有向边
indgree[l[cur][i]]--;
if(!indgree[l[cur][i]])
q.push(l[cur][i]);
}
}
if(n > ) return ;//当n>0时，说明有节点未排序则表示节点关系有冲突
else return ;
}
邻接矩阵：
int indgree[MAXN], map[MAXN][MAXN];
int n;
stack <int> ss;
bool topsort(){
int i, j;
while(){
for(i = ; i <= n; ++i)
if(indgree[i] == ) break;
if(i != n + ){
for(j = ; j <= n; ++j)
if(map[i][j] == ){
map[i][j] = ;
--indgree[j];
}
indgree[i] = -;
ss.push(i);
}
else break;
}
bool flag = true;
for(i = ; i <= n; ++i){
for(j = ; j <= n; ++j){
if(map[i][j] == ){
flag = false;
}
}
}
return flag;
} void print(){
while(!ss.empty()){
printf("%d ",ss.top());
ss.pop();
}
printf("\n");
}