Puzzle: Wagiri

题目大意

给你一个$n$个点$m$条边的连通图，每条边有“Lun”,”Qie”两种权值，问是否可以选择一些边，使得所有点联通，并使得选择的权值为”Lun”的边在至少一个环中，权值为”Qie”的边不在环中。若不能输出”NO”，若能输出”YES”，并输出边的数量和具体的边。

解题思路

边在环中恰好符合边的双连通分量定义，直接对所有权值为”Lun”形成的图做点的双连通分量缩点，接着枚举所有权值为”Lun”的边，若该边的两端点在对应缩点编号相同，就说明这个边一定在至少一个环中；若编号不相同，则满足条件，该边必须删掉。然后对剩下的点求生成树，判断能否构成完整的生成树。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define debug(a) cout<<#a<<"="<<a<<endl;
#define int long long
//#define x first
//#define y second
typedef long long LL;
typedef pair<int,int> PII;
typedef pair<double,double> PDD;
const double eps=1e-8;
bool multi=0;

const int N=3e5 + 10,M=1e6 + 10;
int n,m;
int h[N],e[M],ne[M],idx;
int dfn[N],low[N],timestamp;
int stk[N],top;
int id[N],dcc_cnt;
bool is_bridge[M];
int d[N];

void add(int a,int b){
    e[idx]=b,ne[idx]=h[a],h[a]=idx++;
}

struct Edge {
    int u, v, h, st;
}edge[M];

void tarjan(int u,int from){
    dfn[u]=low[u]=++timestamp;
    stk[++top]=u;

    for(int i=h[u];~i;i=ne[i]){
        int j=e[i];
        if(!dfn[j]){
            tarjan(j,i);
            low[u]=min(low[u],low[j]);
            if(dfn[u]<low[j]){
                is_bridge[i]=is_bridge[i^1]=true;
            }
        }else if(i!=(from^1)){
            low[u]=min(low[u],dfn[j]);
        }
    }

    if(dfn[u]==low[u]){
        ++dcc_cnt;
        int y;
        do{
            y=stk[top--];
            id[y]=dcc_cnt;
        }while(y!=u);
    }
}

int p[N];

int find(int x) {
    if(p[x] != x) return p[x] = find(p[x]);
    return p[x];
}

void solve(){
    cin>>n>>m;
    memset(h,-1,sizeof h);
    vector<PII> ans;
    for(int i = 0; i < m; i++) {
        cin >> edge[i].u >> edge[i].v;
        edge[i].st = 1;
        string s;
        cin >> s;
        if(s == "Lun") {
            // ans.push_back({edge[i].u, edge[i].v});
            add(edge[i].u, edge[i].v);
            add(edge[i].v, edge[i].u);
            edge[i].h = 1;
        }else{
            edge[i].h = 0;
        }
    }
    for(int i = 1; i <= n; i++) {
        tarjan(i,-1);
    }

    for(int i=0;i<idx;i++){
        if(is_bridge[i]) 
            d[id[e[i]]]++;
    }

    for(int i = 0; i < m; i++) {
        if(edge[i].h) {
            if(id[edge[i].u] != id[edge[i].v]) {
                edge[i].st = 0;
            }else{
                ans.push_back({edge[i].u, edge[i].v});
            }
        }
    }
    for(int i = 1; i <= dcc_cnt; i++) {
        p[i] = i;
    }
    for(int i = 0; i < m; i++) {
        if(!edge[i].h && edge[i].st) {
            int a = id[edge[i].u], b = id[edge[i].v];
            int pa = find(a), pb = find(b);
            if(pa != pb) {
                ans.push_back({edge[i].u, edge[i].v});
                p[pa] = pb;
            }
        }
    }
    for(int i = 2; i <= dcc_cnt; i++) {
        if(p[find(i)] != p[find(1)]) {
            cout << "NO\n";
            return;
        }
    }
    cout << "YES\n";
    cout << ans.size() << '\n';
    for(auto [a, b]: ans) {
        cout << a << ' ' << b << '\n';
    }


}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int TTT=1;
    if(multi) cin>>TTT;
    while(TTT--){
        solve();
    }

    return 0;
}

Challenge NPC 2

题目大意

给你一个$n$个点$m$条边的无环的森林，问你这棵森林的补图能否找到一条哈密顿路径。

解题思路

首先对于菊花图一定无解。

另外，要在补图找到哈密顿路径，也就是当这两个点没边时，补图中这两点有边。

对于这棵森林可以这样构造路径，从一棵树进去找路径再从另一棵树进去找路径，以此类推。每棵树进去找路径的次数不会超过两次。

接下来考虑每棵树，对于每棵树找到直径路径$path$与直径中点$rt$，$bfs$求树上所有点到$rt$的距离，$vector$用记录每个距离都对应了哪些点，每次找哈密尔顿路径可以先走距离为$1,2,\dots$的结点，但对于相邻距离的两个结点怎么避免原图有边。加入$vector$的过程，我们可以从直径的一端$u$（对于直径长度是奇数的情况，$u$应该是距离$rt$较远的点）到直径的另一端$v$形成的路径依次加入到每个距离对应的$vector$，然后剩下的点依次加到$vector$中，然后依次走距离为$1,2,\dots$的结点，这样就不会有出现相邻走的两点原图有边的情况。这里如果只有距离为$0$或$1$的点，这棵树就必须通过别的树先出去再进来，即需要走两次。但如果只有一棵树，那么无解。

参考代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef pair<int, int> PII;
typedef long long LL;
const int INF = 0x3f3f3f3f3f3f3f3f;

bool multi = 1;

const int N = 5e5 + 10;
int n, m;
vector<vector<int>> adj;
int id[N], tot;
vector<vector<int>> ve;
int dist[N], from[N];
bool st[N];
void dfs1(int u, int father) {
    ve[tot].push_back(u);
    id[u] = tot;
    for(auto v: adj[u]) {
        if(v == father) continue;
        dfs1(v, u);
    }
}

struct Node {
    vector<int> ans1;
    int ans2;
};

void solve(){
    tot = 0;
    cin >> n >> m;
    for(int i = 0; i <= n; i++) {
        id[i] = 0;
    }
    adj.assign(n + 1, vector<int>());
    ve.assign(n + 1, vector<int>());
    for(int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    auto bfs = [&](int root, int cid) {
        for(auto x: ve[cid]) {
            dist[x] = INF;
        }
        queue<int> q;
        q.push(root);
        dist[root] = 0;
        from[root] = 0;
        while(q.size()) {
            int u = q.front();
            q.pop();
            for(auto v: adj[u]) {
                if(dist[v] > dist[u] + 1) {
                    dist[v] = dist[u] + 1;
                    from[v] = u;
                    q.push(v);
                }
            }
        }
    };
    // cerr << 1 << '\n';
    vector<Node> vans;
    for(int i = 1; i <= n; i++) {
        if(id[i]) continue;
        ++tot;
        dfs1(i, -1);
        int rt = i;
        for(auto x: ve[tot]) {
            st[x] = 0;
        }
        bfs(rt, tot);
        int mxd = -1;
        for(auto x: ve[tot]) {
            if(mxd < dist[x]) {
                mxd = dist[x];
                rt = x;
            }
        }
        bfs(rt, tot);
        mxd = -1;
        for(auto x: ve[tot]) {
            if(mxd < dist[x]) {
                mxd = dist[x];
                rt = x;
            }
        }
        int cur = rt;
        vector<int> path;
        while(cur) {
            path.push_back(cur);
            cur = from[cur];
        }
        int tmp = (int)path.size() / 2;
        while(tmp--) {
            rt = from[rt];
        }
        bfs(rt, tot);
        mxd = mxd - mxd / 2;
        vector<vector<int>> vd(mxd + 1);
        for(auto x: path) {
            vd[dist[x]].push_back(x);
            st[x] = 1;
        }
        for(auto x: ve[tot]) {
            if(!st[x]) vd[dist[x]].push_back(x);
        }
        vector<int> ans1;
        int ans2 = 0;
        for(int i = 1; i <= mxd; i++) {
            for(auto x: vd[i]) {
                ans1.push_back(x);
            }
        }
        if(mxd == 0 || mxd > 1) {
            ans1.push_back(vd[0][0]);
        }else{
            ans2 = vd[0][0];
        }
        vans.push_back({ans1, ans2});
    }
    int cnt2 = 0;
    for(int i = 0; i < vans.size(); i++) {
        cnt2 += (vans[i].ans2 > 0);
    }
    for(int i = 0; i < (int)vans.size() - 1; i++) {
        if(!vans[i].ans2) {
            swap(vans[i], vans.back());
        }
    }
    vector<int> ans;
    if(cnt2 == 0) {
        for(int i = 0; i < vans.size(); i++) {
            for(auto x: vans[i].ans1) {
                ans.push_back(x);
            }
        }
    }else if(cnt2 == 1 && tot == 1) {
        // cout << "JDOWJA: " << cnt << ' ' << tot << '\n';
        cout << -1 << '\n';
        return;
    }else{
        for(int i = 0; i < vans.size(); i++) {
            for(auto x: vans[i].ans1) {
                ans.push_back(x);
            }
        }
        for(int i = 0; i < vans.size(); i++) {
            if(vans[i].ans2) {
                ans.push_back(vans[i].ans2);
            }
        }
    }
    for(int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " \n"[i == (int)ans.size() - 1];
    }

}

signed main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    int T = 1;
    if(multi) cin >> T;
    while(T--) {
        solve();
    }

    return 0;
}