| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 156141 | Flying_dragon_02 | 전압 (JOI14_voltage) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define mp make_pair
typedef pair<int, int> ii;
const int mod = 1e9 + 7;
const int inf = 1e9;
int add(int x, int y) {
return (1ll * x + 1ll * y) % mod;
}
int del(int x, int y) {
return ((1ll * x - 1ll * y) % mod + mod) % mod;
}
int mul(int x, int y) {
return (1ll * x * 1ll * y) % mod;
}
const int N = 1e5 + 5;
int n, m, bad[N], badEdge, ans, parity[N], dist[N], low[N];
vector<int> graph[N];
bool vis[N];
int cnt;
void dfs(int u, int p) {
dist[u] = low[u] = ++cnt;
vis[u] = 1;
parity[u] = parity[p] ^ 1;
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i].fi;
if(!vis[v]) {
dfs(v, u);
bad[u] += bad[v];
low[u] = min(low[u], low[v]);
}
else {
if(parity[v] == parity[u]) {
if(dist[v] < dist[u]) {
bad[v]--;
bad[u]++;
badEdge++;
}
}
else
low[u] = min(low[u], dist[v]);
}
}
}
void bfs(int u, int p) {
vis[u] = 1;
for(int i = 0; i < graph[u].size(); i++) {
int v = graph[u][i];
if(v == p) continue;
if(!vis[v]) {
bfs(v, u);
if(bad[v] == badEdge && low[v] > dist[u])
ans++;
}
}
}
int main() {
cin.tie(0), ios_base::sync_with_stdio(0);
cin >> n >> m;
for(int i = 1; i <= m; i++) {
int u, v;
cin >> u >> v;
graph[u].pb(v);
graph[v].pb(u);
}
for(int i = 1; i <= n; i++) {
if(!vis[i])
dfs(i, i);
}
if(badEdge == 1)
ans++;
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {
if(!vis[i])
bfs(i, i);
}
cout << ans;
}