이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define dbg(x) cerr << #x << " = " << x << "\n"
#define fast_io ios_base::sync_with_stdio(0); cin.tie(0); cout.tie()
using namespace std;
using ll = long long;
using ld = long double;
const int N = 1e4;
int pr[N], cnt[N], e[N];
int f(int x) { return (x == pr[x]) ? x : pr[x] = f(pr[x]); }
int main() {
fast_io;
int n, m;
cin >> n >> m;
for (int i = 0; i < n; ++i)
pr[i] = i, cnt[i] = 1, e[i] = 0;
for (int i = 0; i < m; ++i) {
int v, u;
cin >> v >> u;
--v, --u;
if (f(v) == f(u)) ++e[f(v)];
else {
cnt[f(v)] += cnt[f(u)];
e[f(v)] += e[f(u)] + 1;
}
pr[f(u)] = f(v);
}
set <int> s;
for (int i = 0; i < n; ++i)
s.insert(f(i));
if (int(s.size()) > 2)
return void(cout << "NE\n"), 0;
for (int i = 0; i < n; ++i)
if ((cnt[f(i)] * (cnt[f(i)] - 1) / 2) != e[f(i)])
return void(cout << "NE\n"), 0;
cout << "DA\n";
}
# | 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... |
# | 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... |