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 <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <numeric>
using namespace std;
using ll = long long;
#define int ll
#define vi vector<int>
#define fore(i, a, b) for(int i=a; i<b; ++i)
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define pb push_back
const int N = 1010;
vi adj[N];
int adjM[N][N];
bool vis[N];
vi list;
void dfs(int i){
vis[i] = 1;
list.pb(i);
for(int v : adj[i]){
if(vis[v]) continue;
dfs(v);
}
}
signed main(){
int n, m;
cin >> n >> m;
fore(i, 0, m){
int u, v;
cin >> u >> v;
adj[u].pb(v);
adj[v].pb(u);
adjM[u][v] = adjM[v][u] = 1;
}
// at most two complete components
bool ok = 1;
int cnt = 0;
fore(i, 1, n+1){
if(vis[i]) continue;
list.clear();
cnt++;
dfs(i);
fore(j, 0, sz(list)){
fore(k, j+1, sz(list)){
ok &= adjM[list[j]][list[k]];
}
}
}
if(ok && cnt <= 2){
cout << "DA";
} else {
cout << "NE";
}
cout << endl;
}
# | 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... |