제출 #783635

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
783635		makanhulia	Naboj (COCI22_naboj)	C++17	110 / 110	156 ms	24732 KiB

naboj

#include <bits/stdc++.h>
#define int long long
#define fi first
#define se second
#define keish                             ios_base::sync_with_stdio(0);       cin.tie(0); cout.tie(0)
      
using namespace std;

int n, m, u, v;

signed main(){
      keish;
  cin >> n >> m;
      vector<vector<int>> e(n);
      vector<int> deg(n);
      for(int i = 0; i < m; i++){
            cin >> u >> v; u--, v--;
            e[v].push_back(u);
            deg[u]++;
      }

      queue<int> q;
      vector<int> ans;
      for(int i = 0; i < n; i++){
            if(!deg[i]){
                  q.push(i);
                  ans.push_back(i);
            }
      }

      while(!q.empty()){
            int u = q.front(); q.pop();

            for(auto v : e[u]){
                  deg[v]--;
                  if(!deg[v]){
                        q.push(v);
                        ans.push_back(v);
                  }
            }
      }

      for(int i = 0; i < n; i++){
            if(deg[i]){
                  cout << -1 << '\n';
                  return 0;
            }
      }

      cout << ans.size() << '\n';
      for(auto x : ans) cout << x + 1 << " " << 1 << '\n';
}     

• Subtask 1: 15 / 15
• Subtask 2: 25 / 25
• Subtask 3: 70 / 70