给定一个无向图，问需要多少笔才能将图画完
如果一个连通分量是一个孤立的点,只需要0笔.
如果一个连通分量是一个欧拉回路,只需要1笔.
其余的非欧拉图或者存在一条欧拉路径的需要笔数 == 该连通分量中奇数度的点数目 / 2.
所以可以通过并查集来判断连通分量中点的个数。该连通分量中点的数目num[i]和该连通分量中奇度点的个数odd[i].
如果num[i]==0或1,需0笔.(注意num[i]==0表示i点不是根,num[i]==1表示i点是一个孤立的点.)
如果num[i]>1且odd[i]==0 需1笔
如果num[i]>1且odd[i]>0 需odd[i]/2笔
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e5 + 10;
int f[N], n, m, num[N], odd[N], d[N];
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
int main()
{
while(cin >> n >> m){
memset(num, 0, sizeof num);
memset(odd, 0, sizeof odd);
memset(d, 0, sizeof d);
for(int i = 1; i <= n; i ++) f[i] = i;
for(int i = 1; i <= m; i ++){
int a, b;
scanf("%d %d", &a, &b);
d[a] ++ , d[b] ++;
f[find(a)] = find(b);
}
for(int i = 1; i <= n; i ++){
num[find(i)] ++;
if(d[i] % 2) odd[find(i)] ++;
}
int res = 0;
for(int i = 1; i <= n; i ++){
if(num[i] <= 1) continue;
else if(odd[i] == 0) res ++;
else res += odd[i] / 2;
}
printf("%d\n", res);
}
return 0;
}
以下题解转自网络。原文链接：https://blog.csdn.net/l1832876815/article/details/70306197
思路：第一问m达到的最大值为2^k。
第二问可以模拟一下旋转鼓接地线的旋转过程，每次旋转即删去第一个数，然后在最后加一个0(a<<1&((1<<k)-1))或1(a<<1&((1<<k)-1)+1)；
因为所有数为0到2^k-1，对于任意给定的点a，将它与点a1=a<<1&((1<<k)-1)与点a2=a1+1分别连一条边，构成欧拉回路（每个点入度=出度=2），加一个vis数组确定每个数出现一次。因为结果需要按照字典序从小到大排，所以首先输出的必然是k个前导0，然后dfs判断0或1时先判0，再判1，逆序输出即可（dfs回溯）。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1 << 15;
int res[N], st[N], n, cnt;
void dfs(int u)
{
int a = (u << 1) & ((1 << n) - 1);
int b = a + 1;
if(!st[a]){
st[a] = 1;
dfs(a);
res[cnt ++] = 0;
}
if(!st[b]){
st[b] = 1;
dfs(b);
res[cnt ++] = 1;
}
}
int main()
{
while(cin >> n){
memset(st, 0, sizeof st);
memset(res, 0, sizeof res);
cnt = 0;
dfs(0);
printf("%d ", (1 << n));
for(int i = 0; i < n - 1; i ++) printf("%d", 0);
for(int i = cnt - 1; i >= n - 1; i --) printf("%d", res[i]);
cout << endl;
}
return 0;
}
首先可以把木棒两端看成节点，把木棒看成边，这样相同的颜色就是同一个节点.
题目就转变成了 1、图是连通的。2、所有节点的度为偶数，或者有且仅有两个度为奇数的节点。
通过并查集来判断图是否连通，但是需要将字符串转换成整数(可以通过字典树的方法来实现)。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 5e5 + 10;
int f[N * 2], trie[N][30], n, m, d[N], cnt[N];
int insert(char str[])
{
int p = 0;
for(int i = 0; str[i]; i ++){
int x = str[i] - 'a';
if(!trie[p][x]) trie[p][x] = ++ n;
p = trie[p][x];
}
if(!cnt[p]) cnt[p] = ++ m;
return cnt[p];
}
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
int main()
{
char s1[11], s2[11];
for(int i = 0; i < N; i ++) f[i] = i;
while(cin >> s1 >> s2){
int a = insert(s1);
int b = insert(s2);
f[find(a)] = find(b);
d[a] ++, d[b] ++;
}
int num = 0, flg = 1, res = -1;
for(int i = 1; i <= m; i ++){
if(d[i] % 2) num ++;
if(num > 2){
flg = 0;
break;
}
if(res == -1) res = find(i);
else if(res != find(i)){
flg = 0;
break;
}
}
if(flg && (num == 0 || num == 2)) puts("Possible");
else puts("Impossible");
return 0;
}
这个题目给每条边标了一个序号，现在要问你该图中是否存在欧拉回路，如果存在，则输出字典序最小的那条欧拉回路（输入按序走过的所有边标号）。且题目中保证了该无向图是连通的。
为保证字典序最小，可以用 vector 来存边，每个点同时存下邻接点的边和边的序号，对于每个点需要将该点相连的边根据序号排序。
判断欧拉回路是否存在的方法：无向图：图连通，所有顶点都是偶数度。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
typedef pair < int , int > pii;
#define x first
#define y second
const int N = 2010, M = 1000005;
vector < pii > g[N];
int res[N], d[N], cnt, n;
bool st[M];
void dfs(int u)
{
for(int i = 0; i < g[u].size(); i ++){
if(!st[g[u][i].x]){
st[g[u][i].x] = 1;
dfs(g[u][i].y);
res[cnt ++] = g[u][i].x;
}
}
}
int main()
{
int a, b, c;
while(cin >> a >> b && a && b){
for(int i = 0; i < N; i ++) g[i].clear();
memset(d, 0, sizeof d);
cnt = 0;
memset(st, 0, sizeof st);
cin >> c;
g[a].push_back({c, b});
g[b].push_back({c, a});
d[a] ++ , d[b] ++ ;
while(cin >> a >> b && a && b){
scanf("%d", &c);
g[a].push_back({c, b});
g[b].push_back({c, a});
d[a] ++ , d[b] ++ ;
}
int s = -1;
for(int i = 0; i < N; i ++){
if(d[i]){
if(d[i] % 2){
s = -1;
break;
}
if(s == -1){
s = i;
}
sort(g[i].begin(), g[i].end());
}
}
if(s == -1) puts("Round trip does not exist.");
else{
dfs(s);
for(int i = cnt - 1; i >= 0; i --){
printf("%d ", res[i]);
}
printf("\n");
}
}
return 0;
}
每条边必须要正反遍历 2 遍，把一条无向边看成两条相反的有向边即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N = 1e4 + 10, M = 1e5 + 10;
int h[N], ne[M], e[M], idx;
int n, m;
bool st[M];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
void dfs(int u)
{
for(int i = h[u]; ~i; i = ne[i]){
if(!st[i]){
int v = e[i];
st[i] = 1;
dfs(v);
printf("%d\n", u);
}
}
}
int main()
{
memset(h, -1, sizeof h);
cin >> n >> m;
for(int i = 1; i <= m; i ++){
int a, b;
scanf("%d %d", &a, &b);
add(a, b), add(b, a);
}
printf("1\n");
dfs(1);
return 0;
}
单词游戏的输出路径版本，因为要输出最小字典序，所以可以对每个单词先进行排序然后再建边。
然后这个题目还多一个找起点的步骤，如果是欧拉路径就找到起点，欧拉回路的话，就随意起点就可以了
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std;
typedef pair < int , int > pii;
const int N = 1e3 + 10;
vector < pii > g[30];
int din[30], dout[30], f[30], T, n, res[N], cnt;
string str[N];
bool st[30], vis[N];
void init()
{
for(int i = 0; i <= 26; i ++){
f[i] = i; g[i].clear();
}
memset(din, 0, sizeof din);
memset(dout, 0, sizeof dout);
memset(st, 0, sizeof st);
memset(vis, 0, sizeof vis);
cnt = 0;
}
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
void dfs(int u)
{
for(int i = 0; i < g[u].size(); i ++){
if(!vis[g[u][i].first]){
int v = g[u][i].second;
vis[g[u][i].first] = 1;
dfs(v);
res[cnt ++] = g[u][i].first;
}
}
}
int main()
{
cin >> T;
while(T --){
scanf("%d", &n);
for(int i = 1; i <= n; i ++){
cin >> str[i];
}
sort(str + 1, str + 1 + n);
init();
int flg = 1;
for(int i = 1; i <= n; i ++){
int len = str[i].length();
int a = str[i][0] - 'a';
int b = str[i][len - 1] - 'a';
f[find(a)] = find(b);
st[a] = st[b] = 1;
din[b] ++ , dout[a] ++;
g[a].push_back({i, b});
}
int start = 0, end = 0, p = str[1][0] - 'a';
for(int i = 0; i < 26; i ++){
if(st[i]){
if(find(p) != find(i)){
flg = 0;
break;
}
if(din[i] == dout[i]) continue;
if(din[i] == dout[i] + 1) end ++;
else if(dout[i] == din[i] + 1) start ++;
else{
flg = 0;
break;
}
}
}
if(flg && !(!start && !end || start == 1 && end == 1)) flg = 0;
if(flg == 0) puts("***");
else{
start = str[1][0] - 'a';
for(int i = 0; i < 26; i ++){
if(dout[i] == din[i] + 1) start = i;
}
dfs(start);
for(int i = cnt - 1; i >= 0; i --){
cout << str[res[i]];
if(i > 0) printf(".");
}
printf("\n");
}
}
return 0;
}
拓扑排序，输出字典序最小的点的序号。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 510;
int g[N][N], n, m, d[N], res[N], cnt;
void topsort()
{
priority_queue < int , vector < int > , greater < int > > q;
for(int i = 1; i <= n; i ++){
if(!d[i]) q.push(i);
}
while(q.size()){
int t = q.top();q.pop();
res[++ cnt] = t;
for(int i = 1; i <= n; i ++){
if(g[t][i]){
if(-- d[i] == 0) q.push(i);
}
}
}
}
int main()
{
while(cin >> n >> m){
memset(g, 0, sizeof g);
memset(d, 0, sizeof d);
cnt = 0;
for(int i = 1; i <= m; i ++){
int a, b;
scanf("%d %d", &a, &b);
if(g[a][b]) continue; // 有重边。
d[b] ++ ;
g[a][b] ++;
}
topsort();
for(int i = 1; i <= cnt; i ++){
printf("%d", res[i]);
if(i < cnt) printf(" ");
else printf("\n");
}
}
return 0;
}
拓扑排序，因为只需要确定是否只有一个冠军就可以了也就是只需要判断是否只有一个入度为 0 的点即可。还需要将每个单词都离散化。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 2e3 + 10;
int d[N], m, len;
int main()
{
while(cin >> m, m){
memset(d, 0, sizeof d);
unordered_map < string , int > mp;
len = 0;
for(int i = 1; i <= m; i ++){
string a, b;
cin >> a >> b;
if(!mp.count(a)) mp[a] = len ++;
if(!mp.count(b)) mp[b] = len ++;
d[mp[b]] ++;
}
len -- ;
int flg = 0;
for(int i = 0; i <= len; i ++){
if(d[i] == 0) flg ++;
}
if(flg == 1) puts("Yes");
else puts("No");
}
return 0;
}
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10;
int h[N], ne[M], e[M], idx;
int d[N], n, dis[N], m, res[N], cnt;
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
bool topsort()
{
queue < int > q;
for(int i = 1; i <= n; i ++){
if(!d[i]) q.push(i);
}
while(q.size()){
int t = q.front();q.pop();
res[cnt ++] = t;
for(int i = h[t]; ~i; i = ne[i]){
int v = e[i];
if( -- d[v] == 0) q.push(v);
}
}
return cnt == n;
}
int main()
{
while(cin >> n >> m){
memset(h, -1, sizeof h);
idx = 0;
memset(d, 0, sizeof d);
memset(dis, 0, sizeof dis);
cnt = 0;
for(int i = 1; i <= m; i ++){
int a, b;
scanf("%d %d", &a, &b);
add(b, a);
d[a] ++;
}
if(!topsort()) puts("-1");
else{
long long ans = 0;
for(int i = 1; i <= n; i ++) dis[i] = 888;
for(int i = 0; i < cnt; i ++){
int t = res[i];
for(int j = h[t]; ~j; j = ne[j]){
dis[e[j]] = max(dis[e[j]], dis[t] + 1);
}
}
for(int i = 1; i <= n; i ++) ans += dis[i];
cout << ans << endl;
}
}
return 0;
}
1， 如何处理等于号
把所有相等的点利用并查集缩成一个点
2， 如何判定UNCERTAIN
当队列中同时存在两及以上个点时，此时无法判断二者哪个更厉害
3， 如何判定OK / CONFLICT
这个和普通的toposort一样了，只需要判断读出了多少个点即可
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<queue>
using namespace std;
const int N = 1e4 + 10, M = 2e4 + 10;
int h[N], ne[M], e[M], idx;
int d[N], f[N], n, m, a[M], b[M], num;
char c[M];
void add(int a, int b)
{
e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}
int find(int x)
{
if(x != f[x]) f[x] = find(f[x]);
return f[x];
}
void topusort()
{
queue < int > q;
for(int i = 0; i < n; i ++){
if(!d[i] && f[i] == i) q.push(i);
}
int flg = 0, cnt = 0;
while(q.size()){
if(q.size() > 1) flg = 1;
int t = q.front();q.pop();
cnt ++;
for(int i = h[t]; ~i; i = ne[i]){
int v = e[i];
if(-- d[v] == 0) q.push(v);
}
}
if(cnt < num)
puts("CONFLICT");
else if(flg)
puts("UNCERTAIN");
else puts("OK");
}
int main()
{
while(cin >> n >> m){
memset(h, -1, sizeof h);
idx = num = 0;
num = n;
memset(d, 0, sizeof d);
for(int i = 0; i <= n; i ++) f[i] = i;
for(int i = 1; i <= m; i ++){
scanf("%d %c %d", &a[i], &c[i], &b[i]);
if(c[i] == '='){
int fa = find(a[i]), fb = find(b[i]);
if(fa != fb){
num --;
if(fa < fb) swap(fa, fb);
f[fa] = fb;
}
}
}
for(int i = 1; i <= m; i ++){
int fa = find(a[i]), fb = find(b[i]);
if(c[i] == '<'){
add(fb, fa);
d[fa] ++;
}
if(c[i] == '>'){
add(fa, fb);
d[fb] ++;
}
}
topusort();
}
return 0;
}
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 210;
int g[N][N], d[N], n, m, T, res[N], cnt, ans[N];
bool toposort()
{
priority_queue<int> q;
for (int i = 1; i <= n; i++){
if (!d[i])
q.push(i);
}
while (q.size()){
int t = q.top();
q.pop();
res[cnt++] = t;
for (int i = 1; i <= n; i++){
if (g[t][i] && --d[i] == 0)
q.push(i);
}
}
return cnt == n;
}
int main()
{
cin >> T;
while (T--){
cin >> n >> m;
memset(g, 0, sizeof g);
memset(d, 0, sizeof d);
cnt = 0;
for (int i = 1; i <= m; i++){
int a, b;
scanf("%d %d", &a, &b);
if (!g[b][a]){
g[b][a] = 1;
d[a]++;
}
}
if (!toposort())
puts("-1");
else{
for (int i = 0, j = n; i < cnt; i++, j--){
ans[res[i]] = j;
}
for (int i = 1; i <= n; i++){
printf("%d", ans[i]);
if (i < n)
printf(" ");
else
printf("\n");
}
}
}
return 0;
}
