T1

带权并查集 f:首位魔法师，wz：该魔法师与首位魔法师的距离,cd：该魔法阵有多少魔法师

#include<iostream>
using namespace std;
const int N = 30005;
struct node{
  int f;
  int wz;
  int cd;
};
int n,m;
node a[N];

int find(int x){
  if(a[x].f==x) return x;
  int t=a[x].f;
  a[x].f=find(t);
  a[x].wz=a[x].wz+a[t].wz-1;
  return a[x].f;
}

void join(int x,int y){
  int tx=find(x),ty=find(y);
  if(tx!=ty){
    a[tx].f=ty;
    a[tx].wz+=a[ty].cd;
    a[ty].cd+=a[tx].cd;
  }
}

void query(int x,int y){
  int tx=find(x),ty=find(y);
  if(tx!=ty){
    cout<<-1<<endl;
    return ;
  }
  int mx=max(a[x].wz,a[y].wz);
  int mn=min(a[x].wz,a[y].wz);
  cout<<mx-mn-1<<endl;
}
int main(){
  cin>>n;
  for(int i=1;i<=30000;i++){
    a[i].f=i;
    a[i].wz=1;
    a[i].cd=1;
  }
  while(n--){
    char c;
	int x,y; 
    cin>>c>>x>>y;
    if(c=='M') join(x,y);
    else query(x,y);
  }
  return 0;
}

T2

#include<bits/stdc++.h>
using namespace std;
int n,k,f[300001];
int find(int x){
    if(f[x]==x) return x;
    return f[x]=find(f[x]);
}
void join(int x,int y){
    int a=find(f[x]),b=find(d[x]);
    f[a]=b;
}
int main(){
    cin>>n>>k;
    int ans=0;
    for(int i=1;i<=n*3;i++) f[i]=i;
    int z,x,y;
    for(int i=1;i<=k;i++){
      cin>>z>>x>>y;
      if(x>n||y>n){
        ans++;
      }
      else{
          if(z==1){
            if(find(x+n)==find(y)||find(x+2*n)==find(y)) ans++;
            else{
                join(x,y);
                join(x+n,y+n);
                join(x+2*n,y+2*n);
            }
          }
          else{
            if(x==y||find(x)==find(y)||find(x+2*n)==find(y)) ans++;
            else{
               	join(x,y+2*n); 
				        join(x+n,y);
				        join(x+2*n,y+n);
            }
          }
      }
    }

    cout<<ans;	
	return 0;
}

T3

bfs+dp 在bfs搜索中更新最短路径数：dp[b]=(dp[b]+dp[a])%mod

#include<bits/stdc++.h>
using namespace std;
int n,m;
vector<int> v[200003];
int mod=1000000007;
int dp[200003];
int ds[200003];
void bfs(int x){
	queue<int> q;
	q.push(x);
	while(q.size()){
    int a=q.front();
    q.pop();
    for(int i=0;i<v[a].size();i++){
    	int b=v[a][i];
    	if(ds[b]==0||ds[b]==ds[a]+1){
    		if(!ds[b]){
    			ds[b]=ds[a]+1;
    			q.push(b);
			}
			dp[b]=(dp[b]+dp[a])%mod;
		}
	}
}
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++){
        int x,y;
        cin>>x>>y;
        v[x].push_back(y);
        v[y].push_back(x);
    }
    dp[1]=1;
    ds[1]=1;
    bfs(1);
    cout<<dp[n];
    return 0;
}

T4

类似于斐波那契数列 如果第i地板没有坏：dp[i]=(dp[i-1]+dp[i-2])%mod;

#include<bits/stdc++.h>
using namespace std;
int mod=1000000007;
int dp[100003]; 
bool b[100003];
int n,m;
int main(){
    cin>>n>>m;
    for(int i=1;i<=m;i++) {
        int a;
        cin>>a;
        b[a]=1;
    }
    dp[0]=1;
    dp[1]=1;
    if(b[1]) dp[1]=0;
    for(int i=1;i<=n;i++){
        if(!b[i]) dp[i]=(dp[i-1]+dp[i-2])%mod;
    }
    cout<<dp[n];
    return 0;
}