Loading... 给定一个有 NN 个节点和 MM 条边的无向图，节点编号为 **１～ｎ** 你需要将每个节点染成黑色或者白色两种颜色之一。接下来会根据节点的颜色 来生成所有边的颜色。每条边连接两个节点，只有其中一个节点是黑色、另一个节点是白色时该边会被染成黑色，否则该边会被染成白色。 请你求出，有多少条边满足，存在一种对于节点染色的方案，使得只有这条边是白色，其它 M - 1M−1 条边都是黑色。 ### 输入格式 第一行两个空格分隔的正整数 $$N,M$$。 接下来 M 行，第 i 行有两个空格分隔的正整数 $$A_i ,B_i (A_i != B_i)$$ 不保证图是连通的，也不保证没有重边。 ### 输出格式 一行一个整数，代表答案。 ### 数据范围 对于所有测试数据， $$ 2 ≤ N ≤ 10^5, 1 ≤ M ≤ 2 \times 10_5 2≤N≤10 $$ 输出时每行末尾的多余空格，不影响答案正确性 要求使用「文件输入输出」的方式解题，输入文件为 `coloring.in`，输出文件为 `coloring.out` **样例输入1** ``` 4 5 1 2 1 3 1 4 2 4 3 4 ``` **样例输出1** ``` 1 ``` **样例解释1** 只有第三条边满足条件，方案为:将节点 11 和 44 染成白色，节点 22 和 33 染成黑色(如下图，用虚线表示白色的边;下同)。 **样例输入2** ``` 4 4 1 2 2 3 3 2 4 3 ``` **样例输出2** ``` 2 ``` **样例解释2** 只有第一条或第四条边满足条件(如下图)。 **样例输入3** ``` 13 16 1 6 2 6 3 1 3 2 4 7 4 7 5 9 6 5 8 2 8 13 9 11 10 3 11 10 11 12 12 8 13 6 ``` **样例输出3** ``` 3 ``` ### code ```cpp //#define NoFile #ifndef _GLIBCXX_NO_ASSERT #include <cassert> #endif #include <cctype> #include <cerrno> #include <cfloat> #include <ciso646> #include <climits> #include <clocale> #include <cmath> #include <csetjmp> #include <csignal> #include <cstdarg> #include <cstddef> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <algorithm> #include <bitset> #include <complex> #include <deque> #include <exception> #include <fstream> #include <functional> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <iterator> #include <limits> #include <list> #include <locale> #include <map> #include <memory> #include <new> #include <numeric> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stack> #include <stdexcept> #include <streambuf> #include <string> #include <typeinfo> #include <utility> #include <valarray> #include <vector> #define FILENAME coloring #define strdef(arg) #arg #define strdef2(arg) strdef(arg) #define INFILE strdef2(FILENAME.in) #define OUTFILE strdef2(FILENAME.out) #define asm asm #define auto auto #define bool bool #define break break #define case case #define catch catch #define char char #define class class #define const const #define const_cast const_cast #define continue continue #define default default #define delete delete #define do do #define double double #define dynamic_cast dynamic_cast #define else else #define enum enum #define explicit explicit #define export export #define extern extern #define false false #define float float #define for for #define friend friend #define goto goto #define if if #define inline inline #define int int #define long long #define mutable mutable #define namespace namespace #define new new #define operator operator #define private private #define protected protected #define public public #define register register #define reinterpret_cast reinterpret_cast #define return return #define short short #define signed signed #define sizeof sizeof #define static static #define static_cast static_cast #define struct struct #define switch switch #define template template #define this this #define throw throw #define true true #define try try #define typedef typedef #define typeid typeid #define typename typename #define union union #define unsigned unsigned #define using using #define virtual virtual #define void void #define volatile volatile #define wchar_t wchar_t #define std std #define brokenpoems brokenpoems using namespace std; namespace io { template <typename _tp> inline bool read(_tp& tp) { char ch = getchar(),opt = tp = 0; while(!isdigit(ch)) { if(EOF == ch)return true; opt |= ('-' == ch); ch = getchar(); } while(isdigit(ch)) { tp = (tp << 1) + (tp << 3) + (ch ^ '0'); ch = getchar(); } if(opt)tp = -tp; return false; } template <typename _tp> inline void out(const _tp& tp) { if(tp < 0)putchar('-'),out(-tp); else (tp > 9) ? (out(tp / 10)) : ((void)NULL),putchar(tp % 10 + '0'); } } namespace brokenpoems { using namespace io; const int maxn = 1e5 + 7,maxm= 4e5 + 7; struct Map { int e_size,n,m,id,time; int head[maxn],col[maxn],low[maxn]; int dfn[maxn],sum[maxn],dep[maxn]; struct edge { int next,to; edge(int a = 0,int b = 0):next(a),to(b) {} } e[maxm]; Map(){ e_size=1; } inline void init() { read(n),read(m); int x,y; for(register int i = 1; i <= m; ++i) { read(x),read(y); add_edge(x,y); add_edge(y,x); } } inline void add_edge(int from,int to) { e[++e_size]=edge(head[from],to); head[from]=e_size; } bool check(int x) { bool flg = 0; for(register int i = head[x]; i; i=e[i].next) { if(!col[e[i].to]) { col[e[i].to] = 3 - col[x]; flg |= check(e[i].to); } else { flg |= col[e[i].to] == col[x]; } } return flg; } void coloring() { id = 0; for(register int i = 1; i <= n; ++i) { if(!col[i]) { col[i] = 1; if(check(i)) { if(!id) id = i; else { puts("0"); exit(0); } } } } } int tarjan(int x,int eid) { dfn[x] = low[x] = ++time; int res = 0; for(register int i = head[x]; i; i=e[i].next) { if(i == eid)continue; if(!dfn[e[i].to])res += tarjan(e[i].to,i ^ 1); low[x] = min(low[x],low[e[i].to]); if(low[e[i].to] > dfn[x])res++; } return res; } int dfs(int x,int eid) { int res = 0; dep[x] = dep[e[eid].to] + 1; for(register int i = head[x]; i ; i = e[i].next) { if(i != eid) { if(!dep[e[i].to]) { res += dfs(e[i].to,i ^ 1); sum[x] += sum[e[i].to]; } else if(dep[e[i].to] < dep[x]) { if((dep[x] - dep[e[i].to]) & 1) { --sum[x]; ++sum[e[i].to]; } else { ++sum[x]; --sum[e[i].to]; ++res; } } } } return res; } void Solve() { init(); coloring(); if(!id) { int cnt = 0; for(register int i = 1; i <= n; ++i) if(!dfn[i]) cnt += tarjan(i,0); out(cnt); cout<< id <<endl; } else { int cnt = dfs(id,0),ans = 0; for(register int i = 1; i <= n; ++i) { ans += sum[i] == cnt; } out(ans + (cnt == 1)); // cout<< id <<endl; } } } M; void main() { M.Solve(); } } int main() { #ifndef NoFile freopen(INFILE,"r",stdin); freopen(OUTFILE,"w",stdout); #endif brokenpoems::main(); } ``` 最后修改：2020 年 10 月 04 日 © 允许规范转载 打赏 赞赏作者 支付宝微信 赞 0 如果觉得我的文章对你有用，请随意赞赏
