不积跬步,无以千里。
这两天主要是复习了图的连通性相关的题+听了youwike哥哥讲课。
先是复习了缩点,割点,割边,点双,边双,2-SAT,感觉比较需要注意的是割点的那个第一个节点的判断,写题的时候总是容易忘。然后又写了几道练习题。
- 缩点
#include <iostream>
#include <cstring>
using namespace std;
const int N = 1e5 + 10;
int n, m, tot, cnt, top, scc, ans;
int a[N], s[N], sta[N], x[N], y[N], f[N];
int head[N], dfn[N], low[N], col[N];
bool vis[N];
struct Map { int to, nxt; } e[N << 1];
void add(int u, int v) {
e[++tot] = {v, head[u]};
head[u] = tot;
}
void tarjan(int u) {
low[u] = dfn[u] = ++cnt;
vis[u] = 1, sta[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v]) {
tarjan(v);
low[u] = min(low[u], low[v]);
} else if(vis[v])
low[u] = min(low[u], dfn[v]);
}
if(dfn[u] == low[u]) {
scc++;
while(sta[top + 1] != u) {
col[sta[top]] = scc;
s[scc] += a[sta[top]];
vis[sta[top--]] = 0;
}
}
}
void dfs(int x) {
if(f[x]) return;
f[x] = s[x];
int maxx = 0;
for(int i = head[x]; i; i = e[i].nxt) {
int v = e[i].to;
if(!f[v]) dfs(v);
maxx = max(maxx, f[v]);
}
f[x] += maxx;
}
int main() {
cin >> n >> m;
for(int i = 1; i <= n; ++i) cin >> a[i];
for(int i = 1, u, v; i <= m; ++i)
cin >> x[i] >> y[i], add(x[i], y[i]);
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= tot; ++i) e[i] = {0, 0};
for(int i = 1; i <= n; ++i) head[i] = 0;
tot = 0;
for(int i = 1; i <= m; ++i)
if(col[x[i]] != col[y[i]]) add(col[x[i]], col[y[i]]);
for(int i = 1; i <= scc; ++i) {
if(!f[i])
dfs(i), ans = max(ans, f[i]);
}
cout << ans << endl;
return 0;
}
- 点双
#include <iostream>
#include <vector>
using namespace std;
const int N = 4e6 + 10;
int n, m, tot, top, cnt, scc;
int s[N];
int head[N], dfn[N], low[N];
vector <int> ans[N];
struct Map { int to, nxt; } e[N << 1];
void add(int u, int v) {
e[++tot] = {v, head[u]};
head[u] = tot;
}
void tarjan(int u, int fa) {
int son = 0;
low[u] = dfn[u] = ++cnt;
s[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v]) {
son++, tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] >= dfn[u]) {
scc++;
while(s[top + 1] != v) ans[scc].push_back(s[top--]);
ans[scc].push_back(u);
}
} else if(v != fa) low[u] = min(low[u], dfn[v]);
}
if(fa == 0 && son == 0) ans[++scc].push_back(u);
}
int main() {
cin >> n >> m;
for(int i = 1, u, v; i <= m; ++i)
cin >> u >> v, add(u, v), add(v, u);
for(int i = 1; i <= n; ++i)
if(!dfn[i]) top = 0, tarjan(i, 0);
cout << scc << endl;
for(int i = 1; i <= scc; ++i) {
cout << ans[i].size() << ' ';
for(int j = 0; j < ans[i].size(); ++j)
cout << ans[i][j] << ' ';
cout << endl;
}
return 0;
}
- 2-SAT
#include <iostream>
using namespace std;
const int N = 2e6 + 10;
int n, m, tot, cnt, scc, top;
int head[N], dfn[N], low[N];
int s[N], col[N];
bool vis[N];
struct Map { int to, nxt; } e[N << 1];
void add(int u, int v) {
e[++tot] = {v, head[u]};
head[u] = tot;
}
void tarjan(int u) {
low[u] = dfn[u] = ++cnt;
vis[u] = 1, s[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++scc;
while(u != s[top + 1]) {
col[s[top]] = scc;
vis[s[top--]] = 0;
}
}
}
int main() {
cin >> n >> m;
for(int i = 1, u, v, vu, vv; i <= m; ++i) {
cin >> u >> vu >> v >> vv;
add(u + n * (vu & 1), v + n * (vv ^ 1));
add(v + n * (vv & 1), u + n * (vu ^ 1));
}
for(int i = 1; i <= (n << 1); ++i)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; ++i)
if(col[i] == col[n + i])
return cout << "IMPOSSIBLE" << endl, 0;
cout << "POSSIBLE" << endl;
for(int i = 1; i <= n; ++i)
cout << (col[i] < col[n + i]) << ' ';
return 0;
}
- 满汉全席
把\(m\)和\(h\)看成两个对立的限制然后直接像2-SAT一样建图就行了,要注意的是对于每组数据都要全部初始化。
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2e6 + 10;
int T, n, m, tot, cnt, scc, top;
int head[N], dfn[N], low[N];
int s[N], col[N];
char s1[110], s2[110];
bool vis[N];
struct Map { int to, nxt; } e[N << 1];
void add(int u, int v) {
e[++tot] = {v, head[u]};
head[u] = tot;
}
void tarjan(int u) {
low[u] = dfn[u] = ++cnt;
vis[u] = 1, s[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to;
if(!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else if(vis[v]) low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++scc;
while(u != s[top + 1]) {
col[s[top]] = scc;
vis[s[top--]] = 0;
}
}
}
void Main() {
cin >> n >> m;
for(int i = 1; i <= tot; ++i) e[i] = {0, 0};
memset(head, 0, sizeof(head)), memset(dfn, 0, sizeof(dfn));
memset(low, 0, sizeof(low)), memset(s, 0, sizeof(s));
memset(col, 0, sizeof(col)), memset(vis, 0, sizeof(vis));
tot = cnt = scc = top = 0;
for(int i = 1, u, v, vu, vv; i <= m; ++i) {
cin >> s1 >> s2, u = v = 0;
int lu = strlen(s1), lv = strlen(s2);
vu = (s1[0] == 'm'), vv = (s2[0] == 'm');
for(int j = 1; j < lu; ++j) u = u * 10 + s1[j] - '0';
for(int j = 1; j < lv; ++j) v = v * 10 + s2[j] - '0';
add(u + n * (vu & 1), v + n * (vv ^ 1));
add(v + n * (vv & 1), u + n * (vu ^ 1));
}
for(int i = 1; i <= (n << 1); ++i)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= n; ++i)
if(col[i] == col[n + i])
return cout << "BAD" << endl, void();
cout << "GOOD" << endl;
}
int main() {
cin >> T;
while(T--) Main();
return 0;
}
- Redundant Paths G
因为是双向边,所以缩点之后就肯定是一棵树,然后要至少度数是2,所以最好的方法就是每两个缩点之后的叶子节点连边,所以答案就是\((s-1)/2\)(s是叶子节点个数)
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6 + 10;
int n, m, tot = 1, top;
int cnt, scc, ans;
int head[N], u[N], v[N], d[N];
int dfn[N], low[N], s[N], col[N];
bool vis[N];
struct Map { int to, nxt; bool flag; } e[N * 2];
void add(int u, int v) {
e[++tot] = {v, head[u], 0};
head[u] = tot;
}
void tarjan(int u) {
low[u] = dfn[u] = ++cnt;
s[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
if(vis[i]) continue;
vis[i] = vis[i ^ 1] = 1;
int v = e[i].to;
if(!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++scc;
while(u != s[top + 1]) col[s[top--]] = scc;
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i)
cin >> u[i] >> v[i], add(u[i], v[i]), add(v[i], u[i]);
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= m; ++i)
if(col[u[i]] != col[v[i]]) d[col[u[i]]]++, d[col[v[i]]]++;
for(int i = 1; i <= scc; ++i)
if(d[i] == 1) ans++;
cout << (ans + 1) / 2 << endl;
return 0;
}
- Running In The Sky
缩点板子题,就多维护一个路径最大值就行了。
#include <iostream>
#include <vector>
using namespace std;
const int N = 2e6 + 10;
int n, m, tot = 1, top;
int cnt, scc, ans;
int head[N], u[N], v[N], d[N];
int dfn[N], low[N], s[N], col[N];
bool vis[N];
struct Map { int to, nxt; bool flag; } e[N * 2];
void add(int u, int v) {
e[++tot] = {v, head[u], 0};
head[u] = tot;
}
void tarjan(int u) {
low[u] = dfn[u] = ++cnt;
s[++top] = u;
for(int i = head[u]; i; i = e[i].nxt) {
if(vis[i]) continue;
vis[i] = vis[i ^ 1] = 1;
int v = e[i].to;
if(!dfn[v])
tarjan(v), low[u] = min(low[u], low[v]);
else low[u] = min(low[u], dfn[v]);
}
if(low[u] == dfn[u]) {
++scc;
while(u != s[top + 1]) col[s[top--]] = scc;
}
}
int main() {
cin >> n >> m;
for(int i = 1; i <= m; ++i)
cin >> u[i] >> v[i], add(u[i], v[i]), add(v[i], u[i]);
for(int i = 1; i <= n; ++i)
if(!dfn[i]) tarjan(i);
for(int i = 1; i <= m; ++i)
if(col[u[i]] != col[v[i]]) d[col[u[i]]]++, d[col[v[i]]]++;
for(int i = 1; i <= scc; ++i)
if(d[i] == 1) ans++;
cout << (ans + 1) / 2 << endl;
return 0;
}
- 菜肴制作
容易发现,如果直接按照限制做的话是不对的,因为不是要最后字典序最小,而是要当前没有输出的数尽量靠前。但是可以发现越大的书越靠后肯定是不劣的,所以只用倒着拓扑就行了。
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
int T, n, m, cnt;
int in[N], ans[N];
vector <int> v[N];
priority_queue <int> q;
void Main() {
cin >> n >> m;
cnt = 0;
for(int i = 1; i <= n; ++i)
in[i] = ans[i] = 0, v[i].clear();
for(int i = 1, u, vv; i <= m; ++i) {
cin >> u >> vv;
in[u]++, v[vv].push_back(u);
}
for(int i = 1; i <= n; ++i)
if(!in[i]) q.push(i);
while(!q.empty()) {
int u = q.top();
q.pop();
for(int i = 0; i < v[u].size(); ++i) {
int y = v[u][i];
in[y]--;
if(!in[y]) q.push(y);
}
ans[++cnt] = u;
}
if(cnt < n) return cout << "Impossible!" << endl, void();
for(int i = cnt; i; --i) cout << ans[i] << ' ';
cout << endl;
}
int main() {
cin >> T;
while(T--) Main();
return 0;
}
感觉缩点很好使啊,就是考试没见过
标签:总结,int,top,20240916,scc,dfn,low,include From: https://www.cnblogs.com/roselu/p/18416600