C++ 解法, 执行用时: 53ms, 内存消耗: 728KB, 提交时间: 2021-12-17

#include<bits/stdc++.h>
using namespace std;
#define debug printf("%d %s\n",__LINE__,__FUNCTION__);fflush(stdout)
using ll=long long;using i64=long long;using db=double;
using u32=unsigned int;using u64=unsigned long long;using db=double;
using pii=pair<int,int>;using vi=vector<int>;
using qi=queue<int>;using pqi=priority_queue<int>;using si=set<int>;
#define pb push_back
#define mk make_pair
#define ins insert
#define era erase
#define fi first
#define se second
#define lowbit(x) x&-x
#define ALL(a) a.begin(),a.end()
const int INF=0x3f3f3f3f;
const ll INFLL=0x3f3f3f3f3f3f3f3f;
const double PI=acos(-1.0);
template<class T>inline bool chkmin(T&a,T b){return b<a?a=b,true:false;}
template<class T>inline bool chkmax(T&a,T b){return a<b?a=b,true:false;}
int _w,_t;FILE* _f;
#define MULTI_CASES

const int N=1e5+5;
int n,m,cnt[N],ans[N],ca;

void solve(){
    ca=0;
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++){
        cnt[i]=0;
    }
    for(int i=1,u,v;i<=m;i++){
        scanf("%d%d",&u,&v);
        if(u^v) ++cnt[v];
    }
    for(int i=1;i<=n;i++){
        if(cnt[i]==n-1){
            ans[++ca]=i;
        }
    }
    printf("%d\n",ca);
    if(ca){
        for(int i=1;i<=ca;i++){
            printf("%d%c",ans[i]," \n"[i==ca]);
        }
    }
    else{
        printf("\n");
    }
}

int main(){
    #ifdef MULTI_CASES
    _w=scanf("%d",&_t);while(_t--)
    #endif
    solve();
    return 0;
}

C++ 解法, 执行用时: 60ms, 内存消耗: 1028KB, 提交时间: 2021-11-08

#include <cstdio>
#include <cstring>

const int N = 100005;
int T, n, m, in_degree[N], out_degree[N];

void solve() {
    for (int i = 1; i <= n; i++) {
        if (in_degree[i] == n-1 && out_degree[i] == 0) {
            printf("1\n%d\n", i);
            return;
        }
    }
    printf("0\n\n");
}

void scan() {
    scanf("%d%d", &n, &m);
    memset(in_degree, 0, (n+1) * sizeof in_degree[0]);
    memset(out_degree, 0, (n+1) * sizeof out_degree[0]);
    for (int i = 0, a, b; i < m; i++) {
        scanf("%d%d", &a, &b);
        if (a == b) continue;
        out_degree[a]++;
        in_degree[b]++;
    }
}

int main() {
    for (scanf("%d", &T); T-- > 0;) scan(), solve();
}