This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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);
}
}
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 && 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);
for(int i = 0; i < M; i++) {
int u, v; scanf("%d %d", &u, &v);
u--; v--;
adj[u].push_back(U.size());
adj[v].push_back(U.size());
U.push_back(u);
V.push_back(v);
}
memset(tin, -1, sizeof(tin));
for(int i = 0; i < N; i++) if(tin[i] == -1) {
dfs0(i, -1);
}
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 (stderr)
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:57: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:74: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:77: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);
~~~~~^~~~~~~~~~~~~~~~~
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |