| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 781639 | Kritzan | Naboj (COCI22_naboj) | C++14 | 0 ms | 0 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <iostream>
#include <utility>
#include <stack>
#include <vector>
#include <queue>
using namespace std;
int n, m;
pair<int ,int> arr[500005];
vector<pair<int ,int> > v[200005];
int ways[200005];
bool vis[200005];
int pnt[200005];
stack<pair<int,int> > s;
queue<int> q;
int main() {
cin >> n >> m;
for(int i =1 ; i <= m; i++) {
int a, b;
cin >> a >> b;
arr[i] = {a, b};
v[a].push_back({b, i});
v[b].push_back({a, i});
pnt[a]++;
ways[a]++;
ways[b]++;
}
memset(vis, 0, sizeof(vis));
for(int i = 1; i <= n; i++) {
if (ways[i] == pnt[i]) {
s.push({i, 1});
q.push(i);
vis[i] = true;
}
else if (pnt[i] == 0){
s.push({i, 0});
q.push(i);
vis[i] = true;
}
}
while(!q.empty()) {
int cur = q.front();
q.pop();
for(int i = 0; i < v[cur].size(); i++) {
int nxt = v[cur][i].first;
int idx = v[cur][i].second;
ways[nxt]--;
ways[cur]--;
pnt[arr[idx].first]--;
if (!vis[nxt] && pnt[nxt] == 0) {
s.push({nxt, 0});
q.push(nxt);
vis[nxt] = true;
}
else if(!vis[nxt] && pnt[nxt] == ways[nxt]) {
s.push({nxt, 1});
q.push(nxt);
vis[nxt] = true;
}
}
}
if (s.size() == n) {
cout << n << endl;
while(!s.empty()) {
cout << s.top().first << " " << s.top().second << endl;
s.pop();
}
}
else {
cout << -1 << endl;
return 0;
}
}