Xmas Contest 2015 B - Broken Christmas Tree
B - Broken Christmas Tree
変なdfsを投げてみたら通った。 計算量がどうなっているのかは分からない。
実装
#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#define repeat(i,n) for (int i = 0; (i) < (n); ++(i))
using namespace std;
void dfs(int i, set<int> & notused, vector<set<int> > const & forbidden, vector<pair<int,int> > & result) {
vector<int> use;
for (int j : notused) {
if (not forbidden[i].count(j)) {
use.push_back(j);
}
}
for (int j : use) {
notused.erase(j);
result.emplace_back(i,j);
}
for (int j : use) dfs(j, notused, forbidden, result);
}
int main() {
int n, m; cin >> n >> m;
vector<set<int> > forbidden(n);
repeat (i,m) {
int p, q; cin >> p >> q;
-- p; -- q;
forbidden[p].insert(q);
forbidden[q].insert(p);
}
set<int> notused; repeat (i,n) notused.insert(i);
vector<pair<int,int> > result;
notused.erase(0);
dfs(0, notused, forbidden, result);
if (result.size() == n-1) {
cout << "Yes" << endl;
for (auto p : result) cout << p.first+1 << ' ' << p.second+1 << endl;
} else {
cout << "No" << endl;
}
return 0;
}