F – Pure

题目描述：

n个点，m条边，问你是否存在一个子图，使得子图每个点的入度和出度都是1

思路：

显然入度等于出度等于1的图是一个环

那么此时只需要去找图中的最小环即可

只有当环的大小最小的时候，才能保证这个子图足够小，才不会存在除了环以外的边与环上的点相连

所以我们可以枚举源点，用spfa来跑最小环，复杂度是O(n * k*m),O(k*m)是跑一次spfa的复杂度

我们需要用fa数组来记录父节点，通过循环求出这个整个环

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 3000 + 50
int n, m, k, x, y;
int tr[MAX];
vector<int>G[MAX];
int fa[MAX];
int ans[MAX];
int dis[MAX];
bool vis[MAX];

int SPFA(int s){
    queue<int>q;
    for(int i = 1; i <= n; ++i)dis[i] = inf;
    mem(vis, 0);
    for(auto v : G[s]){
        vis[v] = 1;
        fa[v] = s;
        q.push(v);
        dis[v] = 1;
    }
    while(!q.empty()){
        int u = q.front();q.pop();
        for(auto v : G[u]){
            if(dis[v] > dis[u] + 1){
                dis[v] = dis[u] + 1;
                fa[v] = u;
                if(!vis[v]){
                    vis[v] = 1;
                    q.push(v);
                }
            }
        }
    }
    return dis[s];
}


void work(){
    cin >> n >> m;
    for(int i = 1; i <= m; ++i){
        cin >> x >> y;
        G[x].push_back(y);
    }
    int minx = inf;
    int id = -1;
    for(int i = 1; i <= n; ++i){
        int d = SPFA(i);
        if(minx > d){
            id = i;
            minx = d;
            for(int i = 1; i <= n; ++i)ans[i] = fa[i];
        }
    }
    if(id == -1){
        cout << -1 << endl;
        return;
    }
    cout << minx << endl;
    vector<int>v;
    v.push_back(id);
    x = ans[id];
    while(x != id){
        v.push_back(x);
        x = ans[x];
    }
    reverse(v.begin(), v.end());
    for(auto x : v)cout << x << endl;
}


int main(){
    io;
    work();
    return 0;
}