前言
今天是camp的第一天（因为几乎啥都不会写了好久，中途还休息了一天，所以发的时候已经是emmmm，开学了QAQ），刚开始还挺轻松的，说了一些背景和故事。鼓励的话差不多了，就开始进入正题，介绍了一些图论的基本概念，紧接着就是Dijkstra（放在另一个blog了），这部分还好接受啦，毕竟我也不是一点图论都不会。短暂休息了一下，开始讲tarjan，这不是我一直没填坑的“图上删边”的关键算法吗！听完之后感觉有点懵，但是又不知道哪里懵，没有完全理解QAQ。最后又休息了一会儿，然后快速过了一个tarjan的题目，开始2-sat，这个就几乎完全懵了╯︿╰。To my surprise，群友都说太简单了?。中午结束的时候，饿得几乎走不动了QAQ。
tarjan
强连通
在有向图G中，两个节点u和v互相可达，则称u和v是强连通的。如果G中任意两个节点互相可达，则称这张图是强连通图。
强连通分量
如果一个有向图G不是强连通图，那么可以把它分成多个子图，其中每个子图鱼的内部是强连通的，而且这些子图不能与子图外的任意点强连通，称这样的一个“极大强连通”子图是G的一个强连通分量（Strongly Connected Components，SCC）。
定理
一个SCC，从其中任意点出发，都至少有一条路径能绕回自己。
迷宫城堡
Problem Description
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。
Input
输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了一条通道可以从A房间来到B房间。文件最后以两个0结束。
Output
对于输入的每组数据，如果任意两个房间都是相互连接的，输出"Yes"，否则输出"No"。
Sample Input
3 3
1 2
2 3
3 1
3 3
1 2
2 3
3 2
0 0
Sample Output
Yes
No
Author
Gardon
我的代码
#include <bits/stdc++.h>
#define int long long
const int N = 1e5 + 5;
std::stack<int> sta;
int dfn[N],low[N],cnt = 0,c[N],tot = 0,siz[N];
std::vector<int> edge[N];
bool b[N];
void init(){//初始化
cnt = 0;
tot = 0;
std::memset(dfn , 0 , sizeof (dfn));
std::memset(low , 0 , sizeof (low));
std::memset(siz , 0 , sizeof (siz));
while (!sta.empty()){
sta.pop();
}
for(int i = 0 ; i < N ; i ++){
edge[i].clear();
}
}
void tarjan(int x){
dfn[x] = low[x] = ++ cnt;//第一次到达这个位置，标记
sta.push(x);
b[x] = true;
for(auto y : edge[x]){
if(!dfn[y]){//如果y没有走过，说明y是x的子节点
tarjan(y);
low[x] = std::min(low[x] , low[y]);//y能到达的地方x一定能到达，所以让low[x]的值指向最远的祖先
}else{
if(b[y])//说明y是x的祖先
low[x] = std::min(low[x] , dfn[y]);
}
}
if(low[x] == dfn[x]){//x是强连通分量的根节点
++ tot;//染色
while (1){//利用栈的性质，一旦x == y说明x的所有子孙已经被处理好了
int y = sta.top();
sta.pop();
b[y] = false;
c[y] = tot;
siz[tot] ++;
if(x == y) break;
}
}
}
signed main() {
std::ios::sync_with_stdio(0);
std::cin.tie(0);
std::cout.tie(0);
int n,m;
while (std::cin >> n >> m) {
if(n == 0 && m == 0) break;
init();
for(int i = 1;i <= m;i ++){
int a , b;
std::cin >> a >> b;
edge[a].push_back(b);
}
for(int i = 1;i <= n;i ++){
if(! dfn[i])
tarjan(i);
}
if(tot == 1){//只有一个强连通分量，说明图上所有点都是连通的
std::cout << "Yes\n";
}else{
std::cout << "No\n";
}
}
return 0;
}
题目分析
拓扑排序
拓扑排序要解决的问题是给一个有向无环图的所有节点排序。就是在不破坏节点先后顺序的前提下，把DAG拉成一条链，使得排在前面的节点不能依赖于排在后面的节点。
Kahn算法
1、找到所有入度为0的点，放入队列q中，作为起点。如果找不到起点，说明这个图不是DAG。不存在拓扑排序
2、获取队首元素u的值，并弹出，将u的所有边删除，可简单处理为与u相连的节点的入度- 1，如果重新出现了入度为0的点，放入q中作为心动2起点。
3、不断重复上面的过程，直到q为空
【模板】拓扑排序 / 家谱树
题目描述
有个人的家族很大，辈分关系很混乱，请你帮整理一下这种关系。给出每个人的后代的信息。输出一个序列，使得每个人的后辈都比那个人后列出。
输入格式
第 \(1\) 行一个整数 \(N\)（\(1 \le N \le 100\)），表示家族的人数。接下来 \(N\) 行，第 \(i\) 行描述第 \(i\) 个人的后代编号 \(a_{i,j}\)，表示 \(a_{i,j}\) 是 \(i\) 的后代。每行最后是 \(0\) 表示描述完毕。
输出格式
输出一个序列，使得每个人的后辈都比那个人后列出。如果有多种不同的序列，输出任意一种即可。
样例 #1
样例输入 #1
5
0
4 5 1 0
1 0
5 3 0
3 0
样例输出 #1
2 4 5 3 1
我的代码
#include<bits/stdc++.h>
#define int long long
const int N = 105;
int in[N],out[N];
int n;
std::vector<int> edge[N];
std::queue<int> q;
void topological(){
for(int i = 1;i <= n;i ++){
if(!in[i]) {
std::cout << i << " ";
q.push(i);
}
}
while (!q.empty()){
int u = q.front();
q.pop();
for(auto v : edge[u]){
in[v] --;
if(!in[v]){
std::cout << v << " ";
q.push(v);
}
}
}
}
signed main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
std::cin >> n;
for(int i = 1 ; i <= n ; i ++){
while (1) {
int t;
std::cin >> t;
if (t == 0) break;
edge[i].push_back(t);
out[i]++;
in[t]++;
}
}
topological();
return 0;
}
题目分析
topological就是对上述过程的简单模拟
基于DFS的拓扑排序
DFS深度搜索的原理，是沿着一条路径一直搜索到最底层，然后逐层回退。这个过程正好体现了点和点的先后关系，天然符合拓扑排序的原理。
一个DAG，如果只有一个点u是0入度的，那么从u开始DFS，DFS递归返回的顺序就是拓扑排序（是一个逆序）。DFS递归返回的首先是最底层的点，它一定是0出度点，没有后续点，是拓扑排序的最后一个点；然后逐步回退，最后输出的是起点u；输出的顺序是逆序。
Following Orders
题面翻译
给定一串变量以及部分变量的大小关系，求所有满足这些关系的排列（由小到大）
题目描述
输入格式
输出格式
样例 #1
样例输入 #1
a b f g
a b b f
v w x y z
v y x v z v w v
样例输出 #1
abfg
abgf
agbf
gabf
wxzvy
wzxvy
xwzvy
xzwvy
zwxvy
zxwvy
我的代码
#include<bits/stdc++.h>
const int N = 30;
int edge[N][N];
std::vector<int> characters;
int in[N];
int topo[N];
bool vis[N];
int f = 0;
void dfs(int x , int cnt){
topo[cnt] = x;
if(cnt == characters.size() - 1){
for(int i = 0 ; i <= cnt ; i ++){
char t = topo[i] + 'a';
std::cout << t;
}
std::cout << "\n";
return ;
}
vis[x] = 1;
for(auto i:characters){
if(!vis[i] && edge[x][i]){
in[i] --;
}
}
for(auto i:characters){
if(!vis[i] && !in[i]){
dfs(i , cnt + 1);
}
}
for(auto i:characters){
if(!vis[i] && edge[x][i]){
in[i] ++ ;
}
}
vis[x] = 0;
}
int main(){
std::string s;
int f = 0;
while (getline(std::cin,s)) {
if(f){
std::cout << '\n';
}
f = 1;
for(int i = 0 ; i < N ; i ++){
std::memset(edge[i] , 0 , sizeof (edge[i]));
}
characters.clear();
std::memset(in , 0 , sizeof(in));
std::memset(topo , 0 , sizeof(topo));
std::memset(vis , 0 , sizeof(vis));
for (int i = 0; i < s.size(); i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
characters.emplace_back(s[i] - 'a');
}
}
std::sort(characters.begin(), characters.end());
getline(std::cin, s);
bool flag = true;
char begin, end;
for (int i = 0; i < s.size(); i++) {
if (s[i] >= 'a' && s[i] <= 'z') {
if (flag) {
begin = s[i];
} else {
end = s[i];
}
if (!flag) {
edge[begin - 'a'][end - 'a'] = 1;
in[end - 'a']++;
}
flag = !flag;
}
}
for(auto i : characters){
if(in[i] == 0) dfs(i,0);
}
}
return 0;
}
题目分析
这题的每组测试样例之间需要用换行隔开
首先我们对数据进行处理，为了方便，我们不妨将每个字符串减去'a'后，存入整型vector中，对所有的节点排序后，按拓扑序输出的各个节点天然有序。
最后按照类似上述BFS的原理，修改成dfs即可，注意回溯。
2-sat
有n个bool变量，其中一些bool变量之间存在制约关系；用所有n个bool变量组成序列，判断是否存在满足所有制约关系的序列，这称为SAT(Satisfiability)问题。如果每个限制关系只涉及两个变量，就是2-SAT问题。
实际背景
有n对夫妻被邀请参加一个聚会，因为场地的问题，每对夫妻中只有1人可以列席。在2n 个人中，某些人之间有着很大的矛盾（当然夫妻之间是没有矛盾的），有矛盾的2个人是不会同时出现在聚会上的。有没有可能会有n 个人同时列席？
用图论来描述2-sat问题
假设原命题公式有 $ x_1 ， x_2 ， x_3 ， ... ， x_n $ ， 共\(n\)个命题变元，那么有\(2n\)个文字(如：\(x_1\) 和 \(\lnot x_1\))
学过离散数学的朋友们都知道，"\(\rightarrow\)"可表示为图论中的"可达"，用"\(\rightarrow\)"连接的命题变元存在这样的关系：
\(a\rightarrow b \Longleftrightarrow \lnot a \vee b\)
现在我们对每个命题变元进行讨论：
1、$ x_i \rightarrow \lnot x_i \Longleftrightarrow \lnot x_i \vee \lnot x_i $ ，说明\(x_i\)为假
2、$ \lnot x_i \rightarrow x_i \Longleftrightarrow x_i \vee x_i $ ，说明\(x_i\)为真
3、$ x_i \Longleftrightarrow \lnot x_i $ ，原命题矛盾，说明不存在满足制约关系的序列
4、\(x_i、\lnot x_i\) 互相不可达，那么\(x_i\)可以随意赋值
我们不妨以\(a_1，a_2\)和\(b_1，b_2\)，这两对夫妻为例，已知\(a_1\)和\(b_2\)之间有矛盾，为了满足制约关系，我们不妨让 \(a_1 \rightarrow b_1\) 、$ b_2 \rightarrow a_2 $ 表示\(a_1\)参加的话一定是\(b_1\)参加，\(b_2\)参加的话一定是\(a_2\)参加。
建完边之后我们不妨用tarjan来划分SCC，同一个SCC中的点表示，选了其中一个，那么必须选择这个SCC中的其他点。如果存在\(a_1 ，a_2\)在同一个SCC中，则为3的情况，说明原命题矛盾。构造可行的方案只需要将，不矛盾的SCC拼起来即可。
根据我们上面的说明我们不难得到下面的解题步骤：
1、根据限制条件建图
2、使用tarjan求出SCC
3、如果每个SCC内都没有夫妻，则说明有合法的出席组合
那么我们应该如果求解一个合法的组合呢？
根据 伍昱 -《由对称性解 2-sat 问题》 我们可以知道：如果要输出一个2-SAT问题的可行解，需要将缩点后构造的新图进行topo排序，自底向上进行选择，最后输出结果
【模板】2-SAT 问题
题目描述
有 \(n\) 个布尔变量 \(x_1\)\(\sim\)\(x_n\)，另有 \(m\) 个需要满足的条件，每个条件的形式都是 「\(x_i\) 为 true / false 或 \(x_j\) 为 true / false」。比如 「\(x_1\) 为真或 \(x_3\) 为假」、「\(x_7\) 为假或 \(x_2\) 为假」。
2-SAT 问题的目标是给每个变量赋值使得所有条件得到满足。
输入格式
第一行两个整数 \(n\) 和 \(m\)，意义如题面所述。
接下来 \(m\) 行每行 \(4\) 个整数 \(i\), \(a\), \(j\), \(b\)，表示 「\(x_i\) 为 \(a\) 或 \(x_j\) 为 \(b\)」(\(a, b\in \{0,1\}\))
输出格式
如无解，输出 IMPOSSIBLE；否则输出 POSSIBLE。
下一行 \(n\) 个整数 \(x_1\sim x_n\)（\(x_i\in\{0,1\}\)），表示构造出的解。
样例 #1
样例输入 #1
3 1
1 1 3 0
样例输出 #1
POSSIBLE
0 0 0
提示
\(1\leq n, m\leq 10^6\) , 前 \(3\) 个点卡小错误，后面 \(5\) 个点卡效率。
由于数据随机生成，可能会含有（ 10 0 10 0）之类的坑，但按照最常规写法的写的标程没有出错，各个数据点卡什么的提示在标程里。
我的代码
#include <bits/stdc++.h>
#define int long long
const int N = 1e6 + 5;
std::vector<int> edge[2 * N];
std::stack<int> sta;
int dfn[2 * N] , low[2 * N] , color[2 * N] , tot , cnt;
bool vis[2 * N];
void tarjan(int x){//缩点
dfn[x] = low[x] = ++ cnt;
vis[x] = true;
sta.push(x);
for(auto i : edge[x]){
if(!dfn[i]){
tarjan(i);
low[x] = std::min(low[x] , low[i]);
} else{
if(vis[i]) {
low[x] = std::min(low[x], dfn[i]);
}
}
}
if(low[x] == dfn[x]){
tot ++;
while (1){
int t = sta.top();
sta.pop();
color[t] = tot;
vis[t] = false;
if(t == x) break;
}
}
}
void solve(){
int n , m ;
std::cin >> n >> m;
for(int k = 1 ; k <= m ; k ++){
int i , a , j , b;
std::cin >> i >> a >> j >> b;
int nota = a ^ 1 , notb = b ^ 1;//获得非a和非b
edge[i + nota * n].push_back(j + b * n);//存非a -> b
edge[j + notb * n].push_back(i + a * n);//存非b -> a
}
for(int i = 1 ; i <= 2 * n ; i ++){
if(!dfn[i]){
tarjan(i);
}
}
for(int i = 1; i <= n ; i ++){
if(color[i] == color[i + n]){//如果存在a和非a同时在一个SCC中，说明矛盾
std::cout << "IMPOSSIBLE\n";
return ;
}
}
std::cout << "POSSIBLE\n";
for(int i = 1 ; i <= n ; i ++){
if(color[i] > color[i + n]){//选择topo序大的,即topo排序后排在后面的点
std::cout << "1 ";
}else{
std::cout << "0 ";
}
}
std::cout << '\n';
}
signed main(){
std::ios::sync_with_stdio(0);
std::cin.tie(0);std::cout.tie(0);
int t = 1;
// std::cin >> t;
while (t --){
solve();
}
return 0;
}
解释说明
Q：为什么不需要重新建图，再排topo序？
A：在罗老师的《算法竞赛》的2-sat的部分有进行说明，“在求SCC时，已经得到了每个点所属的SCC，SCC的序号就是一个topo序”
Q：topo序要从入度为0的点开始，但是tarjan不是从入度为0的点开始，你怎么能保证topo序是正确的呢？
A：tarjan算法本身是一个递归的写法，第一个被染色（主要是被染色，而不是标记）的点一定是没有后继的点，即为入度为0的点。所以每个点的color值就是它所在的SCC的topo序。