图论（拓扑、强连通分量）专项训练
以下算法若无特殊提及，复杂度一般都为 \(\mathcal{O}(n + m)\) 水平。
study
link
有 \(n\) 个项目，对于某些项目 \(x\) 和 \(y\) ，必须先学完 \(x\) 再开始学 \(y\)。请问能否完成所有项目的学习。
对于 \(30\%\) 的数据，保证 \(1 \le n, m \le 15\)。
对于 \(70\%\) 的数据，保证 \(1 \le n, m \le 1000\)。
对于 \(100\%\) 的数据，保证 \(1 \le n, m \le 10^5, 1 \le T \le10\)。
100 pts 做法
建图后，跑拓扑排序，确定图为 DAG 即可。
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
int T, n, m, d[N];
vector < int > G[N];
void work(){
queue < int > q;
n = read(), m = read();
memset(d, 0, sizeof d);
vector < int > t;
for(int i = 1; i <= n; i++) G[i] = t;
for(int i = 1; i <= m; i++){
int u = read(), v = read();
G[u].push_back(v); d[v]++;
}
int cnt = 0;
for(int i = 1; i <= n; i++)
if(d[i] == 0) q.push(i);
while(!q.empty()){
int u = q.front(); q.pop(); cnt++;
for(auto v : G[u]) if(--d[v] == 0) q.push(v);
}
if(cnt != n) printf("no\n");
else printf("yes\n");
}
int main(){
freopen("study.in", "r", stdin);
freopen("study.out", "w", stdout);
T = read();
while(T--) work();
return 0;
}
star
link
牛栏里有 \(n\) 头奶牛，给定若干组 \((u, v)\) 表示奶牛 \(u\) 喜欢 \(v\)，并且如果 A 喜欢 B，B 喜欢 C，那么 A 也喜欢 C，请你算出有多少头奶牛被所有奶牛喜欢。
对于 \(30\%\) 的数据，保证 \(n \le 20, m \le 50\)。
对于 \(70\%\) 的数据，保证 \(n \le 1000, m \le 10^4\)。
对于 \(100\%\) 的数据，保证 \(n \le 10^5, m \le 5 \times 10^5\)。
100 pts 做法
经典奶牛题。tarjan 缩点后形成一张有向无环图。
如果存在两个以上出度为 \(0\) 的点就不存在“明星奶牛”。
否则唯一出度为 \(0\) 的点中的点数就是答案。
#include<bits/stdc++.h>
#define ll long long
#define N 100005
using namespace std;
int read(){
int x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
int n, m, belong[N], dfn[N], low[N];
int cnt, k, num[N], d[N];
bool instack[N];
vector < int > H[N];
stack < int > st;
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
st.push(u); instack[u] = true;
for(auto v : H[u]){
if(!dfn[v]){
tarjan(v); low[u] = min(low[u], low[v]);
} else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
k++;
while(st.top() != u){
int v = st.top(); st.pop();
belong[v] = k; num[k]++;
instack[v] = false;
}
int v = st.top(); st.pop();
belong[v] = k; num[k]++;
instack[v] = false;
}
return;
}
int main(){
freopen("star.in", "r", stdin);
freopen("star.out", "w", stdout);
n = read(), m = read();
for(int i = 1; i <= m; i++){
int u = read(), v = read();
H[u].push_back(v);
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int u = 1; u <= n; u++){
for(auto v : H[u])
if(belong[u] != belong[v]) d[belong[u]]++;
}
int ans = 0, ans1 = 0;
for(int i = 1; i <= k; i++){
if(d[i] == 0) ans += num[i], ans1++;
}
if(ans1 == 1) printf("%d\n", ans);
else printf("0\n");
return 0;
}
t3
link
在一个有向图中，有 \(n\) 个顶点，给出 \(m\) 对数字 \((u, v)\) 表示需要存在一条从顶点 \(u\) 走到顶点 \(v\) 的路径。让你构造一个这样的图，输出最少需要多少条边。
对于 \(30\%\) 的数据，保证 \(1 \le n \le 5\)。
对于 \(70\%\) 的数据，保证 \(1 \le n \le 200\)。
对于 \(100\%\) 的数据，保证 \(1 \le n, m \le 10^5\)。
30 pts 做法
枚举 \(n\) 个点所有连边情况。复杂度 \(\mathcal{O}(2^m)\)，\(m = n(n-1)/2\)。
100 pts 做法
path
link
给定一张 \(n\) 个点， \(m\) 条边的有向图，你需要判断是否存在两个点 \(u,v\)，使得不存在从 \(u\) 到 \(v\) 的路径，也不存在从 \(v\) 到 \(u\) 的路径。
对于 \(30\%\) 的数据，保证 \(n \le 100, m \le 300\)。
对于 \(70\%\) 的数据，保证 \(n \le 1000, m \le 5000\)。
对于 \(100\%\) 的数据，保证 \(n \le 5 \times 10^4, m \le 10^5, T \le 10\)。
100 pts 做法 1
一眼缩点。然后先考虑一种暴力做法。
用 \(\texttt{bitset}\) 记录每个点能否走到当前点。正反图各跑一遍，如果两次跑出来结果之和不为缩点后的点数的话，那么就说明一定存在一个点不能到达另一个点。
实测该算法在 luogu \(\texttt{C++14} + \texttt{O2}\) 情况下可通过，学校 OJ 被卡。
注意多测清空
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define N 50005
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
int n, m, belong[N], cnt;
int k, dfn[N], low[N], d[N];
int d1[N], f11[N];
bool instack[N];
bitset < N > f1[N];
vector < int > G[N], H[N], G1[N];
stack < int > st;
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
st.push(u); instack[u] = true;
for(auto v : H[u]){
if(!dfn[v]){
tarjan(v); low[u] = min(low[u], low[v]);
} else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
k++;
while(st.top() != u){
int v = st.top(); st.pop();
belong[v] = k;
instack[v] = false;
}
int v = st.top(); st.pop();
belong[v] = k;
instack[v] = false;
}
return;
}
void work(){
n = read(), m = read();
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
vector < int > t; k = cnt = 0;
for(int i = 1; i <= n; i++) G[i] = t, H[i] = t, G1[i] = t;
for(int i = 1; i <= m; i++){
int u = read(), v = read();
H[u].push_back(v);
}
for(int i = 1; i <= n; i++) if(!dfn[i]) tarjan(i);
for(int u = 1; u <= n; u++){
for(auto v : H[u])
if(belong[u] != belong[v]){
G[belong[u]].push_back(belong[v]);
G1[belong[v]].push_back(belong[u]);
d[belong[v]]++; d1[belong[u]]++;
}
}
queue < int > q;
for(int i = 1; i <= k; i++) f1[i].reset(), f1[i][i] = true;
for(int i = 1; i <= k; i++)
if(d[i] == 0) q.push(i);
while(!q.empty()){
int u = q.front(); q.pop();
for(auto v : G[u]){
f1[v] |= f1[u];
if((--d[v]) == 0) q.push(v);
}
}
for(int i = 1; i <= k; i++) f11[i] = f1[i].count();
for(int i = 1; i <= k; i++) f1[i].reset(), f1[i][i] = true;
for(int i = 1; i <= k; i++) if(d1[i] == 0) q.push(i);
while(!q.empty()){
int u = q.front(); q.pop();
for(auto v : G1[u]){
f1[v] |= f1[u];
if((--d1[v]) == 0) q.push(v);
}
}
bool flag = false;
for(int i = 1; i <= k; i++)
if(f11[i] + f1[i].count() != k + 1) flag = true;
if(k == 1) flag = false;
if(flag) printf("yes\n");
else printf("no\n");
}
int main(){
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
int T = read();
while(T--) work();
return 0;
}
100 pts 做法 2
考虑更加简洁的做法。
如果存在两个点同时称为入度为 \(0\) 的点的话，那么就一定存在。
注：关键在 if(!q.empty()) return false;。
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
#define N 50005
using namespace std;
ll read(){
ll x = 0, f = 1; char ch = getchar();
while(!isdigit(ch)) {if(ch == '-') f = -1; ch = getchar();}
while(isdigit(ch)) {x = (x << 3) + (x << 1) + ch - 48; ch = getchar();}
return x * f;
}
int n, m, belong[N], cnt;
int k, dfn[N], low[N], d[N];
bool instack[N];
vector < int > G[N], H[N];
stack < int > st;
void tarjan(int u){
dfn[u] = low[u] = ++cnt;
st.push(u); instack[u] = true;
for(auto v : H[u]){
if(!dfn[v]){
tarjan(v); low[u] = min(low[u], low[v]);
} else if(instack[v]) low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]){
k++;
while(st.top() != u){
int v = st.top(); st.pop();
belong[v] = k;
instack[v] = false;
}
int v = st.top(); st.pop();
belong[v] = k;
instack[v] = false;
}
return;
}
bool topo(){
queue < int > q;
int tot = 0;
for(int i = 1; i <= k; i++)
if(!d[i]) q.push(i);
while(!q.empty()){
int u = q.front(); q.pop();
if(!q.empty()) return false;
tot++;
for(auto v : G[u])
if(!(--d[v])) q.push(v);
}
if(tot == k) return true;
return false;
}
void work(){
n = read(), m = read();
memset(dfn, 0, sizeof dfn);
memset(low, 0, sizeof low);
memset(d, 0, sizeof d);
vector < int > t; k = cnt = 0;
for(int i = 1; i <= n; i++)
G[i] = t, H[i] = t;
for(int i = 1; i <= m; i++){
int u = read(), v = read();
H[u].push_back(v);
}
for(int i = 1; i <= n; i++)
if(!dfn[i]) tarjan(i);
for(int u = 1; u <= n; u++){
for(auto v : H[u])
if(belong[u] != belong[v]){
G[belong[u]].push_back(belong[v]);
d[belong[v]]++;
}
}
if(topo()) printf("no\n");
else printf("yes\n");
}
int main(){
freopen("path.in", "r", stdin);
freopen("path.out", "w", stdout);
int T = read();
while(T--) work();
return 0;
}