제출 #1125403

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1125403		SalihSahin	Naboj (COCI22_naboj)	C++20	110 / 110	540 ms	22348 KiB

naboj

#include <bits/stdc++.h>
#define pb push_back
#define int long long
using namespace std;

const int mod = 998244353;
const int N = 1e5 + 10;
const int inf = 1e17;


int32_t main(){
  int n, m;
  cin>>n>>m;
  vector<int> in(n+1), out(n+1), adj[n+1];

  for(int i = 0; i < m; i++){
    int u, v;
    cin>>u>>v;
    swap(u, v);
    out[u]++;
    in[v]++;
    adj[v].pb(u);
  }

  queue<int> q;
  for(int i = 1; i <= n; i++){
    if(!out[i]) q.push(i);
  }

  vector<int> vis(n+1);
  vector<pair<int, int> > ans;

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

    if(vis[x]) continue;
    vis[x] = 1;

    ans.pb({x, 1});
    for(auto itr: adj[x]){
        out[itr]--;
        if(!out[itr]) q.push(itr);
    }
  }

  if(ans.size() != n){
    cout<<-1<<endl;
  }
  else{
    cout<<n<<endl;
    reverse(ans.begin(), ans.end());
    for(int i = 0; i < n; i++){
        cout<<ans[i].first<<" "<<ans[i].second<<endl;
    }
  }
  return 0;
}

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