Submission #246134

#TimeUsernameProblemLanguageResultExecution timeMemory
246134Vladikus004Ronald (COCI17_ronald)C++14
120 / 120
45 ms3576 KiB
#include <bits/stdc++.h> #define inf 2e9 #define all(v) v.begin(), v.end() using namespace std; typedef long long ll; typedef long double ld; typedef pair <int, int> pii; const int N = 1000 + 3; int n, m, cmp[N], cnt, ed[N], sz[N], _cnt[N]; vector <vector <int> > v; void dfs(int x, int w){ cmp[x] = w; for (auto u: v[x]){ if (cmp[u]) continue; dfs(u, w); } } int main() { ios_base::sync_with_stdio(false); cin.tie(0); #ifdef LOCAL freopen("input.txt", "r", stdin); #endif // LOCAL cin >> n >> m; v.resize(n); for (int i = 0; i < m; i++){ int x, y; cin >> x >> y; --x; --y; v[x].push_back(y); v[y].push_back(x); } for (int i = 0; i < n; i++) if (!cmp[i]) dfs(i, ++cnt); for (int i = 0; i < n; i++){ ed[cmp[i]] += v[i].size(); sz[cmp[i]]++; } if (cnt >= 3){ cout << "NE"; return 0; } int can = 1; for (int i = 1; i <= cnt; i++) if (ed[i] != sz[i] * (sz[i] - 1)) can = 0; if (can) cout << "DA"; else cout << "NE"; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...