边的染色(DFS染色+并查集)

描述

传送门:美团2018年CodeM大赛-复赛 - Problem C

小团有一张$n$个点,$m$条边的无向图$G$,有些边上已经被标记了$0$或$1$,表示它的边权。
现在你需要给剩下的边标记边权为$0$或$1$,求有几种标记的方式满足:
对于G中任意一个环,里面所有边的边权的异或值为$0$。

环的定义如下:
对于任意$k$($k≥2$)个软件包$ \lbrace a_1,a_2,…,a_k \rbrace$,若对于所有的$i<k$满足$a_i$依赖$a_{i+1}$,且$a_1=a_k$成立,则这$k$个软件包构成一个环。

输入描述

第一行两个整数$n$, $m$。

接下来$m$行,每行$3$个整数$u$, $v$, $w$,表示有一条边$(u,v)$,若$w=-1$则这条边上没有标记,否则$w=0$或$1$表示这条边上标记了$w$。

数据保证没有重边和自环。

$1≤n≤100,000$
$0≤m≤min(n*(n-1)/2, 100000)$

输出描述

输出方案数对$998,244,353$取模的值。

示例

输入

1
2
3
4
3 3
1 2 -1
2 3 -1
3 1 -1

输出

1
4

思路

  • 首先判断已经有标记的边有没有不符合条件的环。DFS染色判断或者带权并查集判断即可。
  • 如果已经不符合了,那么方案显然为$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
#include <bits/stdc++.h>
using namespace std;

#pragma optimize("-O3")

typedef long long ll;
typedef long double ld;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;

void go();

int main()
{
#ifndef ONLINE_JUDGE
freopen("1.in", "r", stdin);
freopen("1.out", "w", stdout);
#endif
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
go();
return 0;
}

/****************************************************************************************************/

vector<PII> good;
vector<vector<PII> > G;
VI col, vis, fa;
const int mod = 119 << 23 | 1;

int find(int x) { return fa[x] == x ? x : fa[x] = find(fa[x]); }
bool unite(int x, int y)
{
x = find(x), y = find(y);
if (x == y) return false;
fa[x] = y;
return true;
}

bool dfs(int u, int d)
{
vis[u] = 1;
col[u] = d;
for (auto& e : G[u])
{
int &v = e.first, &w = e.second;
if (vis[v] && (d ^ w ^ col[v])) return false;
if (!vis[v] && !dfs(v, w ^ d)) return false;
}
return true;
}

void go()
{
int n, m;
cin >> n >> m;
G.resize(n + 1);
fa.resize(n + 1);
iota(fa.begin(), fa.end(), 0);
while (m--)
{
static int u, v, w;
cin >> u >> v >> w;
if (~w)
G[u].emplace_back(v, w), G[v].emplace_back(u, w), unite(u, v);
else
good.emplace_back(u, v);
}
vis.resize(n + 1);
col.resize(n + 1);
for (int i = 1; i <= n; i++)
{
if (!vis[i] && !dfs(i, 0))
{
cout << 0 << endl;
return;
}
}
ll ans = 1;
for (auto& e : good)
if (unite(e.first, e.second))
(ans <<= 1) %= mod;
cout << ans << endl;
}
捐助作者
0%