存图
链式前向星
int h[N], idx;struct
{int v, w;int ne;
} e[N];void add(int u, int v, int w)
{e[++idx].v = v;e[idx].w = w;e[idx].ne = h[u];h[u] = idx;
}int main()
{for (int i = h[1]; i; i=e[i].ne){}
}
vector 存图
struct e
{int v, w;
};vector<e> v[N];void add(int u, int v, int w)
{v[u].push_back({v, w});
}
邻接矩阵
G[a][b] 存储边 a->b
邻接表
//加入有向边(x, y), 权值为 z
void add(int x, int y, int z)
{ver[++idx] = y, e[idx] = z;ne[idx] = h[x], h[x] = idx;
}//访问从 x 出发的所有边
for (int i = h[x]; i; i = ne[i])
{int y = ver[i], z = e[i]; // 找到了一条有向边(x, y), 权值为 z
}
// 对于每个点k，开一个单链表，存储k所有可以走到的点。h[k]存储这个单链表的头结点
int h[N], e[N], ne[N], idx;// 添加一条边a->b
void add(int a, int b)
{e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}// 初始化
idx = 0;
memset(h, -1, sizeof h);
图的遍历
深度优先遍历
int dfs(int u)
{st[u] = true; // st[u] 表示点u已经被遍历过for (int i = h[u]; i != -1; i = ne[i]){int j = e[i];if (!st[j]) dfs(j);}
}
宽度优先遍历
queue<int> q;
st[1] = true; // 表示1号点已经被遍历过
q.push(1);while (q.size())
{int t = q.front();q.pop();for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (!st[j]){st[j] = true; // 表示点j已经被遍历过q.push(j);}}
}
最短路径
单源最短路径
Dijkstra
只适用于所有边的长度都是非负数的图
朴素模板
int a[N][N], d[N], n, m;
bool v[N];void dijkstra()
{memset (d, 0x3f, sizeof d); // dist 数组memset (v, 0, sizeof v); // 节点标记d[1] = 0;for (int i = 1; i < n; i++) // 重复进行 n - 1 次{int x = 0;// 找到未标记节点中 dist 最小的for (int j = 1; j <= n; j++)if (!v[j] && (x == 0 || d[j] < d[x])) x = j;v[x] = 1;// 用全局最小值点 x 更新其他节点for (int y = 1; y <= n; y++)d[y] = min (d[y], d[x] + a[x][y]);}
}int main()
{cin >> n >> m;//构建邻接矩阵memset (a, 0x3f, sizeof a);for (int i = 1; i <= n; i++) a[i][i] = 0;for (int i = 1; i <= m; i++) {int x, y, z;scanf("%d%d%d", &x, &y, &z);a[x][y] = min (a[x][y], z);}//求单源最短路径dijkstra();for (int i = 1; i <= n; i++)printf("%d\n", d[i]);
}
int g[N][N]; // 存储每条边
int dist[N]; // 存储1号点到每个点的最短距离
bool st[N]; // 存储每个点的最短路是否已经确定// 求1号点到n号点的最短路，如果不存在则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 0; i < n - 1; i ++ ){int t = -1; // 在还未确定最短路的点中，寻找距离最小的点for (int j = 1; j <= n; j ++ )if (!st[j] && (t == -1 || dist[t] > dist[j]))t = j;// 用t更新其他点的距离for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);st[t] = true;}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}堆优化模板
const int N = 100010, M = 1000010;
int h[N], ver[M], e[M], ne[M], d[N];
bool v[N];
int n, m, idx;// 大根堆(优先队列), pair 的第二维为节点编号
// pair 的第一维为 dist 的相反数(利用相反数变成小根堆)
priority_queue< pair<int, int> > q;void add(int x, int y, int z)
{ver[++idx] = y, e[idx] = z;ne[idx] = h[x], h[x] = idx;
}void dijkstra()
{memset (d, 0x3f, sizeof d); // dist 数组memset (v, 0 ,sizeof v); // 节点标记d[1] = 0;q.push(make_pair(0, 1));while (q.size()){// 取出堆顶int x = q.top().second; q.pop();if(v[x]) continue;v[x] = 1;// 扫描所有出边for (int i = h[x]; i; i = ne[i]){int y = ver[i], z = e[i];if (d[y] > d[x] + z){d[y] = d[x] + z;q.push(make_pair(-d[y], y));}}}
}int main()
{cin >> n >> m;// 构建邻接表for (int i = 1; i <= m; i++){int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);}//求单源最短路径dijkstra();for (int i = 1; i <= n; i++)printf("%d\n", d[i]);
}
typedef pair<int, int> PII;int n; // 点的数量
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储所有点到1号点的距离
bool st[N]; // 存储每个点的最短距离是否已确定// 求1号点到n号点的最短距离，如果不存在，则返回-1
int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<PII>> heap;heap.push({0, 1}); // first存储距离，second存储节点编号while (heap.size()){auto t = heap.top();heap.pop();int ver = t.second, distance = t.first;if (st[ver]) continue;st[ver] = true;for (int i = h[ver]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > distance + w[i]){dist[j] = distance + w[i];heap.push({dist[j], j});}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
Bellman-Ford
int n, m; // n表示点数，m表示边数
int dist[N]; // dist[x]存储1到x的最短路距离struct Edge // 边，a表示出点，b表示入点，w表示边的权重
{int a, b, w;
}edges[M];// 求1到n的最短路距离，如果无法从1走到n，则返回-1。
int bellman_ford()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;// 如果第n次迭代仍然会松弛三角不等式，就说明存在一条长度是n+1的最短路径，由抽屉原理，路径中至少存在两个相同的点，说明图中存在负权回路。for (int i = 0; i < n; i ++ ){for (int j = 0; j < m; j ++ ){int a = edges[j].a, b = edges[j].b, w = edges[j].w;if (dist[b] > dist[a] + w)dist[b] = dist[a] + w;}}if (dist[n] > 0x3f3f3f3f / 2) return -1;return dist[n];
}
SPFA (队列优化的 Bellman-Ford)
const int N = 100010, M = 1000010;
int h[N], ver[M], e[M], ne[M], d[N];
bool v[N];
int n, m, idx;void add(int x, int y, int z)
{ver[++idx] = y, e[idx] = z;ne[idx] = h[x], h[x] = idx;
}void spfa()
{queue<int> q;memset (d, 0x3f, sizeof d); // dist 数组memset (v, 0 ,sizeof v); // 是否在队列中d[1] = 0; v[1] = 1;q.push(1);while (q.size()){// 取出队头int x = q.front(); q.pop();v[x] = 0;// 扫描所有出边for (int i = h[x]; i; i = ne[i]){int y = ver[i], z = e[i];if (d[y] > d[x] + z){// 更新, 把新的二元组插入堆d[y] = d[x] + z;if (!v[y]) q.push(y), v[y] = 1;}}}
}int main()
{cin >> n >> m;// 构建邻接表for (int i = 1; i <= m; i++){int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);}//求单源最短路径spfa();for (int i = 1; i <= n; i++)printf("%d\n", d[i]);
}
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N]; // 存储每个点到1号点的最短距离
bool st[N]; // 存储每个点是否在队列中// 求1号点到n号点的最短路距离，如果从1号点无法走到n号点则返回-1
int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]) // 如果队列中已存在j，则不需要将j重复插入{q.push(j);st[j] = true;}}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}
SPFA 判断图中是否存在负环
int n; // 总点数
int h[N], w[N], e[N], ne[N], idx; // 邻接表存储所有边
int dist[N], cnt[N]; // dist[x]存储1号点到x的最短距离，cnt[x]存储1到x的最短路中经过的点数
bool st[N]; // 存储每个点是否在队列中// 如果存在负环，则返回true，否则返回false。
bool spfa()
{// 不需要初始化dist数组// 原理：如果某条最短路径上有n个点（除了自己），那么加上自己之后一共有n+1个点，由抽屉原理一定有两个点相同，所以存在环。queue<int> q;for (int i = 1; i <= n; i ++ ){q.push(i);st[i] = true;}while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];cnt[j] = cnt[t] + 1;if (cnt[j] >= n) return true; // 如果从1号点到x的最短路中包含至少n个点（不包括自己），则说明存在环if (!st[j]){q.push(j);st[j] = true;}}}}return false;
}
多源最短路径
Floyd
int d[N][N], n, m; // n < 300
int main()
{cin >> n >> m;// 把 d 数组初始化为邻接矩阵memset(d, 0x3f, sizeof d);for (int i = 1; i <= n; i++) d[i][i] = 0;for (int i = 1; i <= m; i++){int u, v, w;cin >> u >> v >> w;dp[u][v] = dp[v][u] = min(dp[u][v], w); }// floyd 求任意两点间最短路径for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)d[i][j] = min(d[i][j], d[i][k] + d[k][j]);// 输出for (int i = 1; i <= n; i++){for(int j = 1; j <= n; j++)printf("%d\n", d[i][j]);puts(""); }
}
初始化：for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = INF;// 算法结束后，d[a][b]表示a到b的最短距离
void floyd()
{for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
打印任意两点间的最短路径
Problem - 1385
- 路径的定义：
path[i][j]记录路径，path[i][j] = u表示起点为i，终点为j的最短路径，从i出发下一个点是u。一条完整的路径是从s出发，查询path[s][j] = u找到下一个点u，然后从u出发，查询path[u][j] = v，下一个点是v，等等；最后到达终点j。 - 路径的计算：第
27行path[i][j] = path[i][k]计算了从i出发的下一个点。因为k在i-j的最短路径上，所以i-k也是最短路径。比较path[i][j]和path[i][k]，他们都表示从i出发的下一个点，且这个点在同一条路径上，所以有path[i][j] = path[i][k]。
const int INF = 0x3fffffff;
const int N = 505;
int n, mp[N][N], a[N], path[N][N];void input()
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
cin >> mp[i][j];
if (mp[i][j] == -1) mp[i][j] = INF;
path[i][j] = j;
}
for (int i = 1; i <= n; i++) cin >> a[i];
}void floyd()
{
for (int k = 1; k <= n; k++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
int len = mp[i][k] + mp[k][j] + a[k];
if (mp[i][j] > len)
{
mp[i][j] = len;
path[i][j] = path[i][k]; // 标记到该点的前一个点
}
else if (len == mp[i][j] && path[i][j] > path[i][k])
path[i][j] = path[i][k]; // 若距离相同，按字典序
}
}void output()
{
int s, t;
while (cin >> s >> t)
{
if (s == -1 && t == -1) break;
printf("From %d to %d :", s, t);
printf("Path: %d", s);
int k = s;
while (k != t) //输出路径从起点直至终点
{
printf("-->%d", path[k][t]);
k = path[k][t];
}
printf("\n");
printf("Total cost : %d", mp[s][t]);
}
}int main()
{
while (cin >> n && n)
{
input();
floyd();
output();
}
}
传递闭包
bool d[N][N];
int n, m;int main()
{cin >> n >> m;for (int i = 1; i <= n; i++) d[i][i] = 1;for (int i = 1; i <= m; i++){int x, y;scanf("%d%d", &x, &y);d[x][y] = d[y][x] = 1;}for (int k = 1; k <= n; k++)for (int i = 1; i <= n; i++)for (int j = 1; j <= n; j++)d[i][j] |= d[i][k] & d[k][j];
}
拓扑排序
BFS 模板
int n, m, cnt;
int topo[maxn], in[maxn];void bfs()
{queue<int> q;for (int i = 1; i <= n; i++)if (!in[i])q.push(i);while (!q.empty()){int a = q.front();q.pop();topo[++cnt] = a;for (int i = h[a]; i; i = ed[i].ne){int b = ed[i].to;if (--in[b] == 0)q.push(b);}}
}int main()
{cin >> n >> m;for (int i = 1; i <= m; i++){int a, b;cin >> a >> b;add(a, b);in[b]++;}bfs();if (cnt < n)puts("有环");for (int i = 1; i <= cnt; i++)cout << topo[i];cout << endl;
}
bool topsort()
{int hh = 0, tt = -1;// d[i] 存储点i的入度for (int i = 1; i <= n; i ++ )if (!d[i])q[++ tt] = i;while (hh <= tt){int t = q[hh ++];for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (-- d[j] == 0)q[++ tt] = j;}}// 如果所有点都入队了，说明存在拓扑序列；否则不存在拓扑序列。return tt == n - 1;
}
DFS 模板
int n, a[maxn], in[maxn];
int topo[maxn];
bool vis[maxn], dir[maxn][maxn]; // dir[i][j]=true表示i、j是先后关系void dfs(int z, int cnt)
{topo[cnt] = z;if (cnt == n){for (int i = 1; i <= n; i++)cout << topo[i];cout << endl;return;}vis[z] = true;for (int i = 1; i <= n; i++){if (!vis[a[i]] && dir[z][a[i]])in[a[i]]--;}for (int i = 1; i <= n; i++){if (!in[a[i]] && !vis[a[i]])dfs(a[i], cnt + 1);}for (int i = 1; i <= n; i++){if (!vis[a[i]] && dir[z][a[i]])in[a[i]]++;}vis[z] = false;
}int main()
{cin >> n;for (int i = 1; i <= n; i++)cin >> a[i];bool flag = true;for (int i = 1; i <= n; i++){int st, ed;if (flag){flag = !flag;cin >> st;continue;}if (!flag){flag = !flag;cin >> ed;dir[st][ed] = 1;in[ed]++;continue;}}for (int i = 1; i <= n; i++)if (!in[a[i]])dfs(a[i], 1);
}
无向图的连通性
定理一：\(T\) 的根节点 \(s\) 是割点，当且仅当 \(s\) 有两个或更多子节点
定理二：\(T\) 的非根节点 \(u\) 是割点，当且仅当 \(u\) 存在一个子节点 \(v\)，\(v\) 及其后代都没有回退边连回 \(u\) 的祖先
割点与割边
时间戳 dfn[i] 记录了节点被访问的顺序，表示第 i 个节点是第几个遍历到的，而 low[i] 数组则记录了节点及其子树中能够回溯到的最早访问时间，表示第 i 个节点不经过深度优先生成树上的边最小能到达的节点的 dfn 值。
const int N = 110;int dfn[N], low[N], idx; // 时间戳和最低时间戳
bool iscut[N];
vector<int> G[N]; // 邻接表存储图void dfs(int u, int fa) // u 的父节点是 fa
{
low[u] = dfn[u] = ++idx; // 初始值
int child = 0; // 孩子数目
for (int i = 0; i < G[u].size(); i++) // 处理 u 的所有子节点
{
int v = G[u][i];
if (!dfn[v]) // v 没访问过
{
child++;
dfs(v, u);
low[u] = min(low[v], low[u]); // 用后代的返回值更新 low 值
if (low[v] >= dfn[u] && u != 1)
// if (low[v] > dfn[u] && u != 1) //求割边
iscut[u] = true; // 标记割点
}
else if (dfn[v] < dfn[u] && v != fa) // 处理回退边
low[u] = min(low[u], dfn[v]);
}
if (u == 1 && child >= 2) // 根节点，有两棵以上不相连的子树
iscut[1] = true;
}int main()
{
int ans, n;
while (scanf("%d", &n) != -1)
{
if (n == 0)
break;
memset(low, 0, sizeof low);
memset(dfn, 0, sizeof dfn);
memset(iscut, false, sizeof iscut);
idx = 0;
ans = 0;
for (int i = 0; i <= n; i++) G[i].clear(); int a, b;
while (scanf("%d", &a) && a)
{
while (getchar() != '\n')
{
scanf("%d", &b);
G[a].push_back(b); G[b].push_back(a); // 无向图，需要添加双向边
}
} dfs(1, 1); for (int i = 1; i <= n; i++) ans += iscut[i]; printf("%d\n", ans);
}
}
双连通分量
求无向图加多少条边变成边双连通图
const int N = 1005;
int n, m, low[N], idx;
vector<int> G[N];void dfs(int u, int fa) // 计算每个点的 low 值
{
low[u] = ++idx;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (v == fa) continue;
if (!low[v]) dfs(v, u);
low[u] = min(low[u], low[v]);
}
}int tarjan()
{
int d[N] = {};
for (int i = 1; i <= n; i++)
for (int j = 0; j < G[i].size(); j++)
if (low[i] != low[G[i][j]]) d[low[i]]++; int res = 0;
for (int i = 1; i <= n; i++)
if (d[i] == 1) res++; return res;
}int main()
{
while (cin >> n >> m)
{
memset(low, 0, sizeof low);
for (int i = 0; i <= n; i++) G[i].clear();
for (int i = 1; i <= m; i++)
{
int a, b; cin >> a >> b;
G[a].push_back(b); G[b].push_back(a);
}
idx = 0;
dfs(1, -1);
int ans = tarjan();
cout << (ans + 1) / 2 << endl;
}
}
有向图的连通性
Kosaraju 算法
判断一个有向图整个图是否强连通
const int N = 10005;
vector<int> G[N], rG[N];
vector<int> S; // 存储第一次 DFS 的结果：标记点的先后顺序
int sccno[N], cnt;
bool vis[N];void dfs1(int u)
{
if (vis[u]) return;
vis[u] = true;
for (int i = 0; i < G[u].size(); i++) dfs1(G[u][i]);
S.push_back(u); // 记录点的先后顺序，标记大的放在 S 的后面
}void dfs2(int u)
{ if (sccno[u]) return;
sccno[u] = cnt;
for (int i = 0; i < rG[u].size(); i++) dfs2(rG[u][i]);
}void Kosaraju(int n)
{
cnt = 0; S.clear();
memset(sccno, 0, sizeof sccno); memset(vis, false, sizeof vis);
for (int i = 1; i <= n; i++) dfs1(i); // 点的编号为 1~n, 递归所有点
for (int i = n - 1; i >= 0; i--)
if (!sccno[S[i]])
{
cnt++;
dfs2(S[i]);
}
}int main()
{
int n, m, u, v;
while (scanf("%d%d", &n, &m), n != 0 || m != 0)
{
for (int i = 0; i < n; i++)
{
G[i].clear();
rG[i].clear();
} for (int i = 0; i < m; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v); // 原图
rG[v].push_back(u); // 反图 }
Kosaraju(n);
printf("%s\n", cnt == 1 ? "Yes" : "No");
}
}
Tarjan 算法
判断一个有向图整个图是否强连通
const int N = 10005;
vector<int> G[N];
int low[N], dfn[N], idx;
int sccno[N], cnt;
int st[N], top;void dfs(int u)
{
st[top++] = u;
low[u] = dfn[u] = ++idx;
for (int i = 0; i < G[u].size(); i++)
{
int v = G[u][i];
if (!dfn[v])
{
dfs(v); // DFS 的最底层，是最后一个 SCC
low[u] = min(low[v], low[u]);
}
else if (!sccno[v]) // 处理回退边
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u]) // 栈底的点是 SCC 的祖先，它的 low = dfn
{
cnt++;
while (1)
{
int v = st[--top];
sccno[v] = cnt;
if (u == v) // 栈底的点是 SCC 的祖先
break;
}
}
}void Tarjan(int n)
{
cnt = top = idx = 0;
memset(sccno, 0, sizeof sccno);
memset(low, 0, sizeof low);
memset(dfn, 0, sizeof dfn);
for (int i = 1; i <= n; i++)
if (!dfn[i]) dfs(i);
}int main()
{
int n, m, u, v;
while (scanf("%d%d", &n, &m), n != 0 || m != 0)
{
for (int i = 0; i <= n; i++) G[i].clear();
for (int i = 0; i < m; i++)
{
scanf("%d%d", &u, &v);
G[u].push_back(v);
}
Tarjan(n);
printf("%s\n", cnt == 1 ? "Yes" : "No");
}
}
基环树
P2607 [ZJOI 2008] 骑士 - 洛谷 | 计算机科学教育新生态
#define int long long
const int N = 1e6 + 10;vector<int> G[N];
int fa[N], val[N], mark;
bool vis[N];
int dp[N][2];void add(int u, int v) // 邻接表建树
{
G[u].push_back(v);
fa[v] = u;
}void dfs(int u)
{ dp[u][0] = 0; // 赋初值：不参加
dp[u][1] = val[u]; // 赋初值：参加
vis[u] = true;
for (int v : G[u])
{
if (v == mark) continue;
dfs(v);
dp[u][1] += dp[v][0]; // 父节点选择，子节点不选
dp[u][0] += max(dp[v][0], dp[v][1]); // 父节点不选，子节点可选可不选
}
}int check(int u) // 在基环树中找环上一个点
{
vis[u] = true;
int f = fa[u];
if (vis[f]) return f; // 第二次访问到，是环上一个点
else return check(f); // 继续向父节点方向找
}int solve(int u) // 检查一棵基环树
{
int res = 0;
mark = check(u); // mark 是基环树的环上一个点
dfs(mark); // 做一次 DFS
res = max(res, dp[mark][0]); // mark 不参加
mark = fa[mark];
dfs(mark); // mark 的父节点不参加，再做一次 DFS
res = max(res, dp[mark][0]);
return res;
}signed main()
{
int n; scanf("%lld", &n);
for (int i = 1; i <= n; i++)
{
int d; scanf("%lld%lld", &val[i], &d);
add(d, i);
}
int ans = 0;
for (int i = 1; i <= n; i++)
if (!vis[i]) ans += solve(i); // 逐棵检查基环树
printf("%lld\n", ans);
}
欧拉路
欧拉路：从图中某个点出发，遍历整个图，图中每条边通过且只通过一次
欧拉回路：起点和终点相同的欧拉路
判断图中是否存在 欧拉路 或 欧拉回路：
- 无向连通图：
图中的点全都是偶点，则存在欧拉回路，任意点都可以是起点和终点
如果只有两个奇点，则存在欧拉路，其中一个奇点是起点，另一个奇点是终点 - 有向连通图 ：
当且仅当该图所有点的度数为0时，存在欧拉回路
只有一个度数为1的点，一个度数为-1的点，其他所有点的度数为0时，存在欧拉路，其中度数为1的点是起点, 度数为-1的点是终点
int G[N][N], in[N];void euler(int u)
{
for (int v = 1; v <= 50; v++)
{
if (G[u][v])
{
G[u][v]--;
G[v][u]--;
euler(v);
cout << v << ' ' << u << endl;
}
}
}int main()
{ int t, cnt = 0;
cin >> t;
while (t--)
{
cnt++;
memset(G, 0, sizeof G);
memset(in, 0, sizeof in);
if (cnt != 1)
cout << endl; cout << "Case #" << cnt << endl;
int k;
cin >> k;
int u, v;
for (int i = 1; i <= k; i++)
{
cin >> u >> v;
G[u][v]++;
G[v][u]++;
in[u]++;
in[v]++;
} bool ok = true;
for (int i = 1; i <= 50; i++)
{
if (in[i] & 1)
{
cout << "some beads may be lost" << endl;
ok = false;
break;
}
}
if (ok)
euler(u);
}
}
2-SAT
P4782 【模板】2-SAT - 洛谷 | 计算机科学教育新生态
const int N = 1e6 + 5;
int cur, h[N << 1];
int low[N << 1], dfn[N << 1];
int sccno[N << 1], idx, cnt;
int st[N << 1], top;
int n, m;struct
{
int v;
int ne;
} e[N << 2];void add(int u, int v)
{
e[++cur].v = v;
e[cur].ne = h[u];
h[u] = cur;
}void Tarjan(int u)
{
st[top++] = u;
low[u] = dfn[u] = ++idx;
for (int i = h[u]; i; i = e[i].ne)
{
int v = e[i].v;
if (!dfn[v])
{
Tarjan(v);
low[u] = min(low[u], low[v]);
}
else if (!sccno[v])
low[u] = min(low[u], dfn[v]);
}
if (low[u] == dfn[u])
{
cnt++;
while (1)
{
int v = st[--top];
sccno[v] = cnt;
if (u == v) break;
}
}
}bool two_SAT()
{
for (int i = 1; i <= 2 * n; i++)
if (!dfn[i]) Tarjan(i); // Tarjan 算法找强连通分量
for (int i = 1; i <= n; i++)
if (sccno[i] == sccno[i + n]) return false; // a和非a在同一个强连通分量，无解
return true;
}int main()
{
scanf("%d%d", &n, &m);
while (m--)
{
int a, b, va, vb;
scanf("%d%d%d%d", &a, &va, &b, &vb);
int nota = va ^ 1, notb = vb ^ 1; // 非a，非b
add(a + nota * n, b + vb * n); // 连边(非a，b)
add(b + notb * n, a + va * n); // 连边(非b，a)
}
if (two_SAT())
{
printf("POSSIBLE\n");
for (int i = 1; i <= n; i++)
printf("%d ", sccno[i] > sccno[i + n]);
}
else printf("IMPOSSIBLE");}