解: 判断是否为二分图即可 ,同时可能有多个连通图 ,需要多次搜索染色 .
说明: 邻接矩阵存图 ,dfs搜索染色 .
时间 4704MS ... 题目给了10000MS 管他呢 .
//#include <bits/stdc++.h>
#include <stdio.h>
#include <string.h>
#include <iostream>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 2009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output
int n,m,k,u,v,flag;
int mp[MS][MS];
int col[MS];
void dfs(int bt){
if(flag) return;
for(int i=1;i<=n;i++){
if(mp[bt][i]){
if(col[i] == col[bt]){
flag = 1;
return;
}
else if(col[i] == -1){
col[i] = !col[bt];
dfs(i);
}
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> k;
for(int o=1;o<=k;o++){
memset(mp,0,sizeof mp);
memset(col,-1,sizeof col);
flag = 0;
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> u >> v;
mp[u][v] = mp[v][u] = 1;
}
for(int i=1;i<=n;i++){
if(col[i] == -1){
col[i] = 0;
dfs(i);
}
}
if(flag){
cout << "Scenario #" << o << ":" << endl;
cout << "Suspicious bugs found!" << endl;
cout << endl;
}
else{
cout << "Scenario #" << o << ":" << endl;
cout << "No suspicious bugs found!" << endl;
cout << endl;
}
}
return 0;
}
说明: 链式前向星存图 ,dfs搜索染色 .
时间 4407MS... 和邻接矩阵差不了多少 ,就当再练一次吧 .
//#include <bits/stdc++.h>
#include <stdio.h>
#include <iostream>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 2009
#define mss 17
using namespace std;
// Notice the data size
// Notice the input and output
int n,m,k,u,v,flag,tot;
int col[MS];
struct node{
int to,ne;
}edge[2000009];
int head[MS];
void add(int u,int v){
edge[tot].to = v;
edge[tot].ne = head[u];
head[u] = tot++;
}
void dfs(int bt){
if(flag) return;
for(int i=head[bt];i!=-1;i=edge[i].ne){
int it = edge[i].to;
if(col[it] == col[bt]){
flag = 1;
return;
}
else if(col[it] == -1){
col[it] = !col[bt];
dfs(it);
}
}
}
int main() {
ios::sync_with_stdio(false);
cin >> k;
for(int o=1;o<=k;o++){
for(int i=0;i<MS;i++) col[i] = head[i] = -1;
flag = tot = 0;
cin >> n >> m;
for(int i=1;i<=m;i++){
cin >> u >> v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){
if(col[i] == -1){
col[i] = 0;
dfs(i);
}
}
if(flag){
cout << "Scenario #" << o << ":" << endl;
cout << "Suspicious bugs found!" << endl;
cout << endl;
}
else{
cout << "Scenario #" << o << ":" << endl;
cout << "No suspicious bugs found!" << endl;
cout << endl;
}
}
return 0;
}
题意: k 组样例 ,每次给出 n 个顶点 m 条边的无向图 ,将整个图的所有顶点填充数字 ,每个顶点 u 可填数字 1，2，3 . 要求 m 条边每条边连接的两个顶点 (u,v) 的填充的数字权值之和为奇数 .问这样的填充方法有多少个 .方案可能很大，取模998244353 .
如果没有则输出0.
解: 先将其分为二分图 ,得到两个集合 X ,Y ,当 X 中填 2 此时 Y 中每个点都有 1 3 两种选择 ,所以有 2^y 种 . 反过来 Y 填 2 则有 2^x 种 ,所以每一个连通图都有 2^x + 2^y 种 . 可能出现多个连通图 ,累乘即可 .
注意要对 2 的次方作打表处理 ,当时傻傻的用快速幂超时 ...
#include <bits/stdc++.h>
#define LL long long
#define Pi acos(-1.0)
#define INF 2147483646
#define eps 1e-9
#define MS 300009
#define mss 17
#define mod 998244353
using namespace std;
// Notice the data size
// Notice the input and output
LL n,m,k,u,v,flag,cx,cy;
LL col[MS],er[MS];
struct node{
LL to,ne;
}edge[MS<<1];
LL head[MS],tc;
void add(LL a,LL b){
edge[tc].to = b;
edge[tc].ne = head[a];
head[a] = tc++;
}
void dfs(LL bt,LL cc){ // bfs也行
if(flag) return;
for(int i=head[bt];i!=-1;i=edge[i].ne){
LL tt = edge[i].to;
if(col[tt] == col[bt]){
flag = 1;
return;
}
else if(col[tt] == -1){
col[tt] = !cc;
if(col[tt] == 0) cx++; // x 集合元素个数++
else cy++; // y 集合元素个数++
dfs(tt,!cc);
}
}
}
int main() {
ios::sync_with_stdio(false);
er[0] = 1;
for(int i=1;i<MS;i++){ // 2 的次方
er[i] = er[i-1]*2LL%mod;
}
cin >> k;
while(k--){
flag = 0;
LL ans = 1;
cin >> n >> m;
for(int i=0;i<=n;i++){
head[i] = col[i] = -1;
}
for(int i=1;i<=m;i++){ // 链式前向星
cin >> u >> v;
add(u,v);
add(v,u);
}
for(int i=1;i<=n;i++){ // 也许有多个连通图
if(col[i] == -1){
cx = cy = 0;
cx++; // 记录 X 集合元素个数
col[i] = 0;
dfs(i,0);
if(flag) break;
ans = ans*(er[cx]+er[cy])%mod;
}
}
if(flag) cout << 0 << endl;
else cout << ans << endl;
}
return 0;
}
原文：https://www.cnblogs.com/Tecode/p/13301200.html