7.20学习资料

常规
1

组员：我、陈仲安、李青宸、徐铭泽、李秉恒
图论3
1.知识点

统计所有点入度

a,b
in[b]+;
 
for(){
	if(in[i]==0){
		q.push(i);
	}
}

while(!q.empty()){
	int u=q.front();
	q.pop();
	for(遍历u出发的所有边){
		in[v]--;
		if(in[v]==0){
			q.push(v);
		} 
	}
}

若队列中的数量不大于一 唯一拓扑序列
优先队列 保证字典序
Tarjan算法：

void tarjan(int x){
	dfn[x]=low[x]=++top;
	vis[x]=1;
	stk.push(x);
	for(int i=head[x];i;i=e[i].next){
		if(!dfn[e[i].to]){
			tarjan(e[i].to);
			low[x]=min(low[x],low[e[i].to]);
		}
		else if(vis[e[i].to]){
			low[x]=min(dfn[e[i].to],low[x]); 
		}
	}
	if(dfn[x]==low[x]){
		cnt++;
		while(stk.top()!=x){
			vis[stk.top()]=0;
			n[stk.top()]=cnt;
			stk.pop();
		}
		vis[x]=0;
		b[x]=cnt;
		stk.pop();
	}
}

二、例题
1.P3387：割点模板
缩点，就是把一张有向有环图中的环缩成一个个点，形成一个有向无环图。
方法：
缩点+拓扑排序+DP
2.P1656：割边模板
枚举一条边，将这条边去掉后随便选一个点进行FloodFill，或者说从这个点开始进行DFS或BFS遍历，看是否能遍历到所有的点。
如果不可以则这条边为割边，否则不是。
3.P3469
两种情况：
如果当前点不是割点，那么删去之后影响不大，只能导致当前被封锁的点到不了其他点，其他点也到不了当前被封锁的点。
如果当前点是割点，那么删去之后会断成几大块儿。对于每一块，到剩下的每一个不属于这一块儿的点都不能继续拜访，设这一块大小为S，总点数为n，那么这一块儿产生的不能拜访数为：Ans+=S×(n−s)。对每一块儿都要这么做。统计答案即可。注意：这个点上面的所有也是一块儿，大小计算方法与求树的重心类似。就是用总点数减去当前点为根的子树大小。

1 个赞