- 判定桥
$(u,v)$ ：$u$ 和$v$ 不在同一边双中，$(u,v)$ 是桥
pii edge[M];
vector<pii> G[N]; //存边标号
int dfn[N], low[N], tot;
stack<int> stk;
bool inST[N];
int grp[N];
void tarjanE(int u, int from) {
dfn[u] = low[u] = ++tot;
stk.push(u);
inST[u] = true;
for (pii e : G[u]) {
if (e.second == from) continue;
int v = e.first;
if (!dfn[v]) {
tarjanE(v, e.second);
low[u] = min(low[u], low[v]);
} else if (inST[v]) {
low[u] = min(low[u], dfn[v]);
}
}
if (dfn[u] == low[u]) {
while (inST[u]) {
int v = stk.top();
stk.pop();
inST[v] = false;
grp[v] = u;
}
}
}pii edge[M];
vector<pii> G[N];
int dfn[N], low[N], tot;
vector<vector<int> > dcc; //存点双边集
bool cut[N];
stack<int> stkE; //存边标号
bool vis[M]; //每条边仅访问一次，因为每条边只属于一个点双
void tarjan_dcc(int u, int from) {
dfn[u] = low[u] = ++tot;
int child = 0;
for (pii e : G[u]) {
if (vis[e.second]) continue;
vis[e.second] = true;
stkE.push(e.second);
int v = e.first;
if (!dfn[v]) {
child++;
tarjan_dcc(v, e.second);
low[u] = min(low[u], low[v]);
if (dfn[u] <= low[v]) { //x是割点，并且搓出个点双边集合
cut[u] = true;
vector<int> tmp;
while (stkE.top() != e.second) {
tmp.push_back(stkE.top());
stkE.pop();
}
stkE.pop();
tmp.push_back(e.second);
dcc.push_back(tmp);
}
} else {
low[u] = min(low[u], dfn[v]);
}
}
if (from == 0 && child < 2) cut[u] = false; //根特殊处理
}- 对于一张
$DAG$ 上的任意拓扑序，对任意点$u$ ，一定不可能到达拓扑序小于$u$ 的点，否则要么成环，要么不符合拓扑 - 对于一张
$DAG$ ，某点$u$ 能被所有点到达的充要条件是：$u$ 是当前唯一出度为$0$ 的点
//匈牙利算法求二分图最大匹配 时间O(Nx*E)
#include <bits/stdc++.h>
using namespace std;
const int maxn = 2005;
vector<int> mp[maxn];
bool used[maxn];
int cx[maxn], cy[maxn];
int Nx, Ny;
void init() {
for (int i = 1; i <= Nx; i++) mp[i].clear();
}
void add_edge(int x, int y) {
mp[x].push_back(y);
}
bool dfs(int x) {
int sz = mp[x].size();
for (int i = 0; i < sz; i++) {
int y = mp[x][i];
if (!used[y]) {
used[y] = true;
if (cy[y] == 0 || dfs(cy[y])) {
cx[x] = y;
cy[y] = x;
return true;
}
}
}
return false;
}
int max_match() {
for (int i = 1; i <= Nx; i++) cx[i] = 0;
for (int i = 1; i <= Ny; i++) cy[i] = 0;
int ans = 0;
for (int i = 1; i <= Nx; i++) {
for (int j = 1; j <= Ny; j++) {
used[j] = false;
}
if (dfs(i)) ans++;
}
return ans;
}
int main() {
int n, m, e;
scanf("%d%d%d", &n, &m, &e);
Nx = n, Ny = m;
init();
for (int i = 0; i < e; i++) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(x, y);
}
printf("%d", max_match());
return 0;
}
/*
Nx为左，Ny为右
cx[],cy[]为匹配成功后情况
cx[i]=j表示左边i连右边j
调用init()前先赋值Nx, Ny
初始化 init();
加边 add_edge(x, y);
二分图最大匹配答案 max_match()
*///Hopcroft-Karp，O(sqrt(n) * m)
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 2005;
const int inf = 0x3f3f3f3f;
const int mod = 1e9 + 7;
vector<int> mp[maxn];
int Nx, Ny, dis;
int dx[maxn], dy[maxn];
int cx[maxn], cy[maxn];
bool used[maxn];
void init() {
for (int i = 1; i <= Nx; i++) mp[i].clear();
}
void add_edge(int x, int y) {
mp[x].push_back(y);
}
bool bfs() {
queue<int> que;
dis = inf;
for (int i = 1; i <= Nx; i++) dx[i] = -1;
for (int i = 1; i <= Ny; i++) dy[i] = -1;
for (int i = 1; i <= Nx; i++) {
if (cx[i] == -1) {
que.push(i);
dx[i] = 0;
}
}
while (!que.empty()) {
int x = que.front(); que.pop();
if (dx[x] > dis) break;
for (int i = 0; i < mp[x].size(); i++) {
int y = mp[x][i];
if (dy[y] == -1) {
dy[y] = dx[x] + 1;
if (cy[y] == -1) dis = dy[y];
else {
dx[cy[y]] = dy[y] + 1;
que.push(cy[y]);
}
}
}
}
return dis != inf;
}
int dfs(int x) {
int sz = mp[x].size();
for (int i = 0; i < sz; i++) {
int y = mp[x][i];
if (!used[y] && dy[y] == dx[x] + 1) {
used[y] = true;
if (cy[y] != -1 && dy[y] == dis) continue;
if (cy[y] == -1 || dfs(cy[y])) {
cx[x] = y;
cy[y] = x;
return 1;
}
}
}
return 0;
}
int max_match() {
for (int i = 1; i <= Nx; i++) cx[i] = -1;
for (int i = 1; i <= Ny; i++) cy[i] = -1;
int ans = 0;
while (bfs()) {
for (int i = 1; i <= Ny; i++) {
used[i] = false;
}
for (int i = 1; i <= Nx; i++) {
if (cx[i] == -1) {
ans += dfs(i);
}
}
}
return ans;
}
int main() {
int n, m, e;
scanf("%d%d%d", &n, &m, &e);
Nx = n, Ny = m;
init();
for (int i = 0; i < e; i++) {
int x, y;
scanf("%d%d", &x, &y);
add_edge(x, y);
}
printf("%d", max_match());
return 0;
}
/*
Nx为左，Ny为右
cx[],cy[]为匹配成功后情况
cx[i]=j表示左边i连右边j
调用init()前先赋值Nx, Ny
初始化 init();
加边 add_edge(x, y);
二分图最大匹配答案 max_match()
*///KM求二分图最佳完备匹配 O(n^3)
struct KM { //by @tokiisukaze
#define type int
#define inf 0x3f3f3f3f
static const int N = 505;
int n, mx[N], my[N], prv[N];
type slk[N], lx[N], ly[N], w[N][N];
bool vx[N], vy[N];
void init(int _n) {
n = _n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
w[i][j] = 0;
}
}
}
void addEdge(int x, int y, type val) { w[x][y] = val; }
void match(int y) { while (y) swap(y, mx[my[y] = prv[y]]); }
void bfs(int x) {
int i, y;
type d;
for (i = 1; i <= n; i++) {
vx[i] = vy[i] = false;
slk[i] = inf;
}
queue<int> q;
q.push(x);
vx[x] = true;
while (true) {
while (!q.empty()) {
x = q.front();
q.pop();
for (y = 1; y <= n; y++) {
d = lx[x] + ly[y] - w[x][y];
if (!vy[y] && d <= slk[y]) {
prv[y] = x;
if (!d) {
if (!my[y]) return match(y);
q.push(my[y]);
vx[my[y]] = true;
vy[y] = true;
} else slk[y] = d;
}
}
}
d = inf + 1;
for (i = 1; i <= n; i++) {
if (!vy[i] && slk[i] < d) {
d = slk[i];
y = i;
}
}
for (i = 1; i <= n; i++) {
if (vx[i]) lx[i] -= d;
if (vy[i]) ly[i] += d;
else slk[i] -= d;
}
if (!my[y]) return match(y);
q.push(my[y]);
vx[my[y]] = true;
vy[y] = true;
}
}
type max_match() {
int i;
type res;
for (i = 1; i <= n; i++) {
mx[i] = my[i] = ly[i] = 0;
lx[i] = *max_element(w[i] + 1, w[i] + n + 1);
}
for (i = 1; i <= n; i++) bfs(i);
res = 0;
for (i = 1; i <= n; i++) res += lx[i] + ly[i];
return res;
}
#undef type
#undef inf
} km;
/*
O(n^3)
km.init(n);
km.addEdge(a,b,val); a,b: 1~n
非常重要:
inf >= abs(max_match())
inf >= abs(max_match())
inf >= abs(max_match())
判断是否完备匹配的方法：
不连接的边赋值-infx (infx 必须远小于 inf, 否则不满足上述 inf 条件)
保证 infx>|N|*|val|
使max_match匹配值离谱
*///dinic最大流
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f3f3f3f3f
struct Dinic {
static const int N = 1010;
struct Edge {
int from, to;
ll cap, flow;
Edge(int u, int v, ll c, ll f) : from(u), to(v), cap(c), flow(f) {}
};
int n, m, s, t;
vector<Edge> edges;
vector<int> G[N];
int d[N], cur[N];
bool vis[N];
void init(int n) {
for (int i = 0; i < n; i++) G[i].clear();
edges.clear();
}
void AddEdge(int from, int to, ll cap) {
edges.push_back(Edge(from, to, cap, 0));
edges.push_back(Edge(to, from, 0, 0));
m = edges.size();
G[from].push_back(m - 2);
G[to].push_back(m - 1);
}
bool BFS() {
memset(vis, 0, sizeof(vis));
queue<int> Q;
Q.push(s);
d[s] = 0;
vis[s] = 1;
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (int i = 0; i < G[x].size(); i++) {
Edge &e = edges[G[x][i]];
if (!vis[e.to] && e.cap > e.flow) {
vis[e.to] = 1;
d[e.to] = d[x] + 1;
Q.push(e.to);
}
}
}
return vis[t];
}
ll DFS(int x, ll a) {
if (x == t || a == 0) return a;
ll flow = 0, f;
for (int &i = cur[x]; i < G[x].size(); i++) {
Edge &e = edges[G[x][i]];
if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
e.flow += f;
edges[G[x][i] ^ 1].flow -= f;
flow += f;
a -= f;
if (a == 0) break;
}
}
return flow;
}
ll Maxflow(int s, int t) {
this->s = s;
this->t = t;
ll flow = 0;
while (BFS()) {
memset(cur, 0, sizeof(cur));
flow += DFS(s, INF);
}
return flow;
}
};
/*
n点m边 s起t终 点编号1~n
init(n) 清空邻接表
AddEdge(from, to, cap) from到to的有向边，流量cap
Maxflow(s, t) s起t终的最大流量
*///最小费用最大流
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
#define INF 0x3f3f3f3f
template<class T>
struct Minimum_Cost_Flow_Dijkstra {
#define N 5050
#define P pair<T, int>
struct edge {
int to;
T cap, cost, rev;
};
T flow, res, dist[N], h[N];
vector<edge> G[N];
int preV[N], preE[N], n;
inline void init(int x) {
n = x;
for (int i = 0; i <= n; i++) {
G[i].clear();
}
}
inline void addEdge(int from, int to, T cap, T cost) {
G[from].push_back((edge) {to, cap, cost, (int) G[to].size()});
G[to].push_back((edge) {from, 0, -cost, (int) G[from].size() - 1});
}
inline void min_cost_flow(int s, int t, T f) {
fill(h + 1, h + 1 + n, 0);
flow = res = 0;
while (f > 0) {
priority_queue<P, vector<P>, greater<P> > D;
memset(dist, INF, sizeof dist);
dist[s] = 0;
D.push(P(0, s));
while (!D.empty()) {
P now = D.top();
D.pop();
if (dist[now.second] < now.first) continue;
int v = now.second;
for (int i = 0; i < (int) G[v].size(); ++i) {
edge &e = G[v][i];
if (e.cap > 0 &&
dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {
dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];
preV[e.to] = v;
preE[e.to] = i;
D.push(P(dist[e.to], e.to));
}
}
}
if (dist[t] == INF) break;
for (int i = 1; i <= n; ++i) {
h[i] += dist[i];
}
T d = f;
for (int v = t; v != s; v = preV[v]) {
d = min(d, G[preV[v]][preE[v]].cap);
}
f -= d;
flow += d;
res += d * h[t];
for (int v = t; v != s; v = preV[v]) {
edge &e = G[preV[v]][preE[v]];
e.cap -= d;
G[v][e.rev].cap += d;
}
}
}
#undef N
#undef P
};
/*
Minimum_Cost_Flow_Dijkstra<T> mcmf;
T为int或ll
记得修改对应INF值
记得修改对应INF值
记得修改对应INF值
mcmf.init(n) 初始化n和邻接表
mcmf.addEdge(from, to, cap, cost) from源点，to汇点，cap边最大流量，cost边单位流量费用
mcmf.min_cost_flow(s, t, INF) 起点，终点，总流量限制
mcmf.flow = 最大流
mcmf.res = 最大流情况下最小费用
使用样例
mcmf.min_cost_flow(s, t, INF);
printf("%d %d\n", mcmf.flow, mcmf.res);
*/- 对于图中任意一个点
$u$ ，对于从$u$ 连出去的所有边，边权最小的一条至少存在于一颗$MST$ 上 - 该结论是
$Prim$ 与$Kruskal$ 的正确性基础 - 在
$Prim$ 中，将当前的生成树视作一个点 - 在
$Kruskal$ 中，将若干连通分量视作若干个点
- 对于任意一个图，若存在多种
$MST$ ，其边权分布不变 - 即若在
$MST_1$ 中有$3$ 条长度$1$ 的边，则在$MST_2$ 中也有$3$ 条长度$1$ 的边 - 同时该结论也意味着不存在
$1+3=2+2$ 的不同$MST$ - bzoj1016
- 对于任意一个连通图，从
$A$ 点走到$B$ 点的所有路径，要使路径上最长的边最小，最小的情况一定出现在$MST$ 中的$Path(A,B)$ 。 - bzoj3732
//基尔霍夫矩阵求无向图最小生成树个数
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 305;
const int mod = 1e9 + 7;
int a[maxn][maxn];
int Gauss(int n) {
int ans = 1;
for (int i = 1; i <= n; ++i) {
for (int k = i + 1; k <= n; ++k) {
while (a[k][i]) {
int d = a[i][i] / a[k][i];
for (int j = i; j <= n; ++j) {
a[i][j] = (a[i][j] - 1LL * d * a[k][j] % mod + mod) % mod;
}
swap(a[i], a[k]);
ans = -ans;
}
}
ans = 1LL * ans * a[i][i] % mod, ans = (ans + mod) % mod;
}
return ans;
}
void addEdge(int u, int v) {
--a[u][v], --a[v][u], ++a[u][u], ++a[v][v];
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
while (m--) {
int u, v;
scanf("%d%d", &u, &v);
addEdge(u, v);
}
printf("%d\n", Gauss(n - 1));
return 0;
}
/*
点 1~n
addEdge(u, v);
ans = Gauss(n - 1);
*/-
欧拉通路：通过图中所有边的简单路
-
欧拉回路：闭合的欧拉路
欧拉回路存在的充要条件
-
无向图：当且仅当该图所有顶点度数都为偶数，且该图是连通图
-
有向图：所有顶点的入度等于出度且该图是连通图
-
混合图
- 无向边随意定向，得到每个点的
$x=deg_{出}-deg{入}$ ，若存在$x$ 为奇数，则不存在 - 另所有
$x:=x/2$ ，建图网络流 - 对于
$x>0$ （出 > 入）的点，加边$(s, i, x)$ - 对于
$x<0$ （入 > 出）的点，加边$(i, t, |x|)$ - 对于随意定向的无向边
$(i, j)$ ，加边$(i, j, 1)$ - 存在满流则存在欧拉回路，将流量为
$1$ 的无向边反转即可得到欧拉图
- 无向边随意定向，得到每个点的
- 定义：存在欧拉通路，不存在欧拉回路
- 充要条件：仅由两个点度数为奇数，这两个点分别为起点和终点
-
从栈顶到栈底输出即为欧拉回路
-
求字典序最小解：优先搜索较小点 / 边
stack<pii> stk;
bool vis[maxn]; // vis 与 cur 大小应开 M
int cur[maxn];
void dfs(int u) {
for (; cur[u] < G[u].size(); cur[u]++) {
int v = G[u][cur[u]].first;
int eid = G[u][cur[u]].second;
if (!vis[eid]) {
vis[eid] = true;
dfs(v);
stk.push({u, v});
}
}
}方法一：二分图染色法，二分图一定不存在奇环，因此判断给出图是否是二分图即可。
方法二：带权并查集。
//带权并查集
int find(int x)
{
if(x==pre[x])return x;
int fa=pre[x];
pre[x]=find(pre[x]);
val[x]^=val[fa];
return pre[x];
}
void solve()
{
scanf("%d",&M);
while(M--)
{
int x,y;
scanf("%d%d",&x,&y);
add_edge(x,y);
add_edge(y,x);
int f1=find(x),f2=find(y);
if(f1!=f2)
{
pre[f1]=f2;
val[f1]=val[x]^val[y]^1;
}
else if(val[x]^val[y]==0)
hasc=1;
}
}tarjan分离出所有边双联通分量，分别检查是否存在偶环。
除非一个边双联通分量仅仅只是一个奇环，否则其中必定存在偶环。
hdu5215，给出n点m边的无重边无自环无向图，求是否存在奇环偶环。
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int maxn = 100005;
const int maxm = 200005;
const int inf = 0x3f3f3f3f;
const int mod = 998244353;
vector<int> e[maxn];
int vis[maxn];
void init(int n) {
for (int i = 1; i <= n; i++) {
e[i].clear();
}
}
bool dfs(int u, int w) {
vis[u] = w;
bool ans = false;
for (int v: e[u]) {
if (vis[v] == -1) {
ans |= dfs(v, w ^ 1);
} else {
if (vis[v] == w) {
ans = true;
}
}
}
return ans;
}
bool oddCircle(int n) {
bool ans = false;
for (int i = 1; i <= n; i++) {
vis[i] = -1;
}
for (int i = 1; i <= n; i++) {
if (vis[i] == -1) {
ans |= dfs(i, 0);
}
}
return ans;
}
int dfn[maxn], low[maxn], idx;
stack<int> stk;
bool inST[maxn];
int pre[maxn];
vector<int> vec[maxn];
void Union(int u, int v) {
pre[v] = u;
}
void tarjan(int u, int fa) {
dfn[u] = low[u] = ++idx;
stk.push(u);
inST[u] = true;
for (int v: e[u]) {
if (v == fa) continue;
if (!dfn[v]) {
tarjan(v, u);
low[u] = min(low[u], low[v]);
} else if (inST[v]) {
low[u] = min(low[u], low[v]);
}
}
if (dfn[u] == low[u]) {
while (stk.top() != u) {
int v = stk.top();
stk.pop();
inST[v] = false;
Union(u, v);
}
stk.pop();
inST[u] = false;
Union(u, u);
}
}
bool check(vector<int> &p) {
map<int, bool> mp;
for (int u: p) {
mp[u] = true;
}
int cntE = 0;
for (int u: p) {
for (int v: e[u]) {
if (mp[v]) cntE++;
}
}
cntE /= 2;
return cntE != p.size() || cntE % 2 == 0;
}
bool evenCircle(int n) {
idx = 0;
for (int i = 1; i <= n; i++) {
dfn[i] = 0;
inST[i] = false;
pre[i] = i;
vec[i].clear();
}
while (!stk.empty()) stk.pop();
for (int i = 1; i <= n; i++) {
if (!dfn[i]) {
tarjan(i, 0);
}
}
for (int i = 1; i <= n; i++) {
vec[pre[i]].push_back(i);
}
bool ans = false;
for (int i = 1; i <= n; i++) {
if (pre[i] == i && vec[i].size() > 2) {
ans |= check(vec[i]);
}
}
return ans;
}
int main() {
int T;
scanf("%d", &T);
while (T--) {
int n, m;
scanf("%d%d", &n, &m);
init(n);
for (int i = 0; i < m; i++) {
int u, v;
scanf("%d%d", &u, &v);
e[u].push_back(v);
e[v].push_back(u);
}
printf("%s\n", oddCircle(n) ? "YES" : "NO");
printf("%s\n", evenCircle(n) ? "YES" : "NO");
}
return 0;
}有的题能卡SPFA但是卡不了BellmanFord，因为BF常数小
SPFA过程中，某个点入队$N$次，即说明存在负环
/*
c[i]表示点i入队次数
有负环 return true
*/
int dis[maxn];
bool inq[maxn];
int c[maxn];
bool checkNegativeRing(int n) {
deque<int> q;
for (int i = 1; i <= n; i++) {
dis[i] = inf;
inq[i] = false;
c[i] = 0;
}
dis[1] = 0;
inq[1] = true;
c[1] = 1;
q.push_back(1);
while (!q.empty()) {
int u = q.front();
q.pop_front();
inq[u] = false;
for (const Edge &e: G[u]) {
int v = e.to, w = e.w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
if (inq[v]) continue;
if (q.empty() || dis[v] < dis[q.front()]) { //SLF优化
q.push_front(v);
} else {
q.push_back(v);
}
inq[v] = true;
if (++c[v] > n) return true;
}
}
}
return false;
}BellmanFord过程中，第$N$轮松弛仍成功，说明存在负环
/*
有负环 return true
*/
bool bellmanFord(int n) {
for (int i = 0; i <= n; i++) dis[i] = inf;
dis[0] = 0;
bool ok;
for (int i = 1; i <= n + 1; i++) {
ok = false;
for (int u = 0; u <= n; u++) {
for (const Edge &e : G[u]) {
int v = e.to, w = e.w;
if (dis[u] + w < dis[v]) {
dis[v] = dis[u] + w;
ok = true;
}
}
}
if (!ok) break;
}
return ok;
}- 若选择
$x$ 后必须选择$y$ ，则从$x$ 向$y$ 建一条边，举例：- 若
$a$ 与$b$ 不能同时选，则建边$a \rightarrow \neg b$ ，$b \rightarrow \neg a$ - 若
$a$ 与$b$ 要么都选要么都不选，则建边$a \rightarrow b$ ，$\neg a\rightarrow \neg b$，$b \rightarrow a$，$\neg b \rightarrow \neg a$ - 若
$a$ 必须选，则建边$\neg a \rightarrow a$ - 若
$a$ 不能选，则建边$a \rightarrow \neg a$ - 按此规则建图
$G$
- 若
- 对
$G$ 进行强连通缩点，得到图$G^{\prime}$ - 若有点
$a$ 与$\neg a$ 属于同一强连通分量，则无解 - 否则必定有解
- 若有点
- 将
$G^{\prime}$ 上的所有边反向，然后跑拓扑求一组合法解- 若当前点可选，选择该点，将与该点矛盾的点标记为不可选
- 若当前点不可选，跳过
- 最后选出的所有点为一组合法解
- 初始化时，注意区分
$n$ 与$n\times2$ ，$maxn$ 开双倍 - 大前提：每个集合仅含
$2$ 个元素
/*
下标从1开始，点映射规则 i->(2i-1, 2i)
init(n) 初始化
addEdge(x, cx, y, cy) 加边
bool solve(int a[]) 求解，返回false表示无解，a[]存解
bool bruteForce(int a[]) 爆搜求字典序最小解，复杂度 O(n*m)
*/
template<class T>
void unique(vector<T> &v) {
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());
}
const int maxn = 1e6 + 7;
struct TwoSat {
// 映射
int pid(int x, int c) {
return x * 2 - 1 + c;
}
// 取非
int rid(int x) {
if (x & 1) return x + 1;
return x - 1;
}
vector<pii> G[maxn * 2];
int n;
int dfn[maxn * 2], low[maxn * 2], tot;
bool inST[maxn * 2];
stack<int> stk;
int grp[maxn * 2];
void tarjan(int u, int from) {
dfn[u] = low[u] = ++tot;
stk.push(u);
inST[u] = true;
for (pii e : G[u]) {
if (e.second == from) continue;
int v = e.first;
if (!dfn[v]) {
tarjan(v, e.second);
low[u] = min(low[u], low[v]);
} else if (inST[v]) {
low[u] = min(low[u], low[v]);
}
}
if (low[u] == dfn[u]) {
while (stk.top() != u) {
grp[stk.top()] = u;
inST[stk.top()] = false;
stk.pop();
}
stk.pop();
grp[u] = u;
inST[u] = false;
}
}
vector<int> rG[maxn * 2], sG[maxn * 2];
void build() {
for (int i = 1; i <= n * 2; i++) {
for (pii e : G[i]) {
int v = e.first;
if (grp[i] == grp[v]) continue;
rG[grp[v]].push_back(grp[i]);
}
}
for (int i = 1; i <= n; i++) {
int gx = grp[pid(i, 0)];
int gy = grp[pid(i, 1)];
sG[gx].push_back(gy);
sG[gy].push_back(gx);
}
for (int i = 1; i <= n * 2; i++) {
if (i != grp[i]) continue;
unique(rG[i]);
unique(sG[i]);
assert(sG[i].size() == 1);
}
}
int in[maxn * 2];
bool vis[maxn * 2];
void top() {
for (int i = 1; i <= n * 2; i++) {
vis[i] = true;
in[i] = 0;
}
for (int i = 1; i <= n * 2; i++) {
for (int v : rG[i]) in[v]++;
}
queue<int> q;
for (int i = 1; i <= n * 2; i++) {
if (!in[i]) q.push(i);
}
while (!q.empty()) {
int u = q.front();
q.pop();
if (vis[u]) {
for (int v : sG[u]) vis[v] = false;
}
for (int v : rG[u]) {
in[v]--;
if (!in[v]) q.push(v);
}
}
}
int eid;
void init(int _n) {
n = _n;
for (int i = 1; i <= n * 2; i++) {
G[i].clear();
rG[i].clear();
sG[i].clear();
dfn[i] = 0;
}
eid = 0;
tot = 0;
}
void addEdge(int x, int cx, int y, int cy) {
G[pid(x, cx)].emplace_back(pid(y, cy), ++eid);
}
bool solve(int a[] = nullptr) {
for (int i = 1; i <= n * 2; i++) {
if (!dfn[i]) tarjan(i, 0);
}
for (int i = 1; i <= n; i++) {
if (grp[pid(i, 0)] == grp[pid(i, 1)]) {
return false;
}
}
build();
top();
if (a != nullptr) {
for (int i = 1; i <= n; i++) {
a[i] = vis[grp[pid(i, 0)]] ? 0 : 1;
}
}
return true;
}
//爆搜求字典序最小方案
vector<int> tmp;
bool dfs(int u) {
if (vis[rid(u)]) return false;
if (vis[u]) return true;
vis[u] = true;
tmp.push_back(u);
for (pii e : G[u]) {
if (!dfs(e.first)) return false;
}
return true;
}
bool bruteForce(int a[]) {
for (int i = 1; i <= n * 2; i++) {
vis[i] = false;
sort(G[i].begin(), G[i].end());
}
for (int i = 1; i <= n * 2; i += 2) {
if (!vis[i] && !vis[i + 1]) {
tmp.clear();
if (!dfs(i)) {
for (int j : tmp) vis[j] = false;
if (!dfs(i + 1)) return false;
}
}
}
for (int i = 1; i <= n; i++) {
a[i] = vis[pid(i, 0)] ? 0 : 1;
}
return true;
}
};团(Clique): n个顶点的完全图
极大团(Maximal Clique): 表示无法是其他团的子团
最大团(Maximum Clique): 点最多的极大团
无向图的最大团=该无向图补图的最大独立集
- 匹配：在$G$中两两没有公共端点的边集合$M\subseteq E$
- 边覆盖：在$G$中的任意顶点都至少是$F$中某条边的端点的边集合$F\subseteq E$（边覆盖所有点）
- 独立集：在$G$中两两互不相连的顶点集合$S\subseteq V$
- 顶点覆盖：在$G$中的任意边都有至少一个端点属于$S$的顶点集合$S\subseteq V$（顶点覆盖所有边）
- 最大匹配$M_{max}$ 最小边覆盖$F_{min}$ 最大独立集$S_{max}$ 最小顶点覆盖$S_{min}$
- 对于任意无孤立点的图：$|M_{max}|+|F_{max}|=|V|$，即【最大匹配数+最小边覆盖数=顶点数】
- 对于任意图：$|S_{max}|+|S_{min}|=|V|$，即【最大独立集数+最小顶点覆盖数=顶点数】
- 在二分图中：$|M_{max}|=|S_{min}|$，即【最大匹配数=最小顶点覆盖数】，因此求出$M_{max}$即可
给定有向图$G=(V, E)$，设$P$是$G$的一个简单路径（顶点不相交）的集合。如果$V$中每个顶点恰好在$P$的一条路上，称$P$为$G$的一个路径覆盖。$P$中路径可以从$V$的任何一个顶点开始，长度任意（可以为0），$G$的最小路径覆盖是$G$的所含路径条数最少的路径覆盖。
简述：选若干条起点任意、长度任意、不经过相同顶点的路径，使得路径覆盖所有顶点，且路径条数最少。
拆分$G$中的所有点
代码待补全