#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MN = 100010;
int N, M;
vector<int> adj[MN], U, V;
int tin[MN], tout[MN], timer, cnt;
struct Fenwick {
vector<int> tree;
void init() {
tree = vector<int>(N + 1, 0);
}
void upd(int idx, int val) {
for(int i = idx + 1; i <= N; i += (i & -i)) tree[i] += val;
}
int quer(int a) {
int ret = 0;
for(int i = a + 1; i >= 1; i -= (i & -i)) ret += tree[i];
return ret;
}
int quer(int a, int b) {
return quer(b) - quer(a - 1);
}
} bit1, bit2;
priority_queue<pii> pq1, pq2;
int ans;
void dfs0(int u, int fe) {
tin[u] = timer++;
for(int i = 0; i < adj[u].size(); i++) {
int e = adj[u][i];
int v = U[e] + V[e] - u;
if(e == fe) continue;
if(tin[v] == -1) {
dfs0(v, e);
}
else if(tin[v] < tin[u]) {
if(tin[v] % 2 == tin[u] % 2) cnt++;
}
}
}
void dfs1(int u, int fe) {
tin[u] = timer++;
for(int i = 0; i < adj[u].size(); i++) {
int e = adj[u][i];
int v = U[e] + V[e] - u;
if(e == fe) continue;
if(tin[v] == -1) {
dfs1(v, e);
}
else if(tin[v] < tin[u]) {
if(tin[v] % 2 == tin[u] % 2) pq1.push({ tin[v], tin[u] }), bit1.upd(tin[u], 1);
else pq2.push({ tin[v], tin[u] }), bit2.upd(tin[u], 1);
}
}
tout[u] = timer;
while(!pq1.empty() && pq1.top().first == tin[u]) bit1.upd(pq1.top().second, -1), pq1.pop();
while(!pq2.empty() && pq2.top().first == tin[u]) bit2.upd(pq2.top().second, -1), pq2.pop();
if(u && bit1.quer(tin[u], tout[u] - 1) == cnt && !bit2.quer(tin[u], tout[u] - 1)) ans++;
}
int main() {
scanf("%d %d", &N, &M);
bool loop = 0;
for(int i = 0; i < M; i++) {
int u, v; scanf("%d %d", &u, &v);
u--; v--;
if(u == v) {
loop++;
continue;
}
adj[u].push_back(U.size());
adj[v].push_back(U.size());
U.push_back(u);
V.push_back(v);
}
if(loop >= 2) {
printf("0");
return 0;
}
memset(tin, -1, sizeof(tin));
for(int i = 0; i < N; i++) if(tin[i] == -1) {
dfs0(i, -1);
}
if(loop) {
if(!cnt) printf("1");
else printf("0");
return 0;
}
memset(tin, -1, sizeof(tin));
timer = 0;
bit1.init();
bit2.init();
for(int i = 0; i < N; i++) if(tin[i] == -1) {
dfs1(i, -1);
}
if(cnt == 1) ans++;
printf("%d", ans);
}
Compilation message
voltage.cpp: In function 'void dfs0(int, int)':
voltage.cpp:34:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
voltage.cpp: In function 'void dfs1(int, int)':
voltage.cpp:49:22: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i = 0; i < adj[u].size(); i++) {
~~^~~~~~~~~~~~~~~
voltage.cpp: In function 'int main()':
voltage.cpp:77:17: error: use of an operand of type 'bool' in 'operator++' is forbidden in C++1z
loop++;
^~
voltage.cpp:87:13: warning: comparison of constant '2' with boolean expression is always false [-Wbool-compare]
if(loop >= 2) {
~~~~~^~~~
voltage.cpp:69:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &N, &M);
~~~~~^~~~~~~~~~~~~~~~~
voltage.cpp:73:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
int u, v; scanf("%d %d", &u, &v);
~~~~~^~~~~~~~~~~~~~~~~
