题意：
rt
解析：
我用的第二种方法。。。
s向所有的边连权值为1的边
所有的点向t连权值为mid的边
如果存在u - > v 则边向u和v分别连一条权值为INF的边
二分mid
用dfs从s 顺着边走标记点
然后输出1 - n种被标记的点即可
#include <iostream>
#include <cstdio>
#include <sstream>
#include <cstring>
#include <map>
#include <cctype>
#include <set>
#include <vector>
#include <stack>
#include <queue>
#include <algorithm>
#include <cmath>
#include <bitset>
#define rap(i, a, n) for(int i=a; i<=n; i++)
#define rep(i, a, n) for(int i=a; i<n; i++)
#define lap(i, a, n) for(int i=n; i>=a; i--)
#define lep(i, a, n) for(int i=n; i>a; i--)
#define rd(a) scanf("%d", &a)
#define rlld(a) scanf("%lld", &a)
#define rc(a) scanf("%c", &a)
#define rs(a) scanf("%s", a)
#define rb(a) scanf("%lf", &a)
#define rf(a) scanf("%f", &a)
#define pd(a) printf("%d\n", a)
#define plld(a) printf("%lld\n", a)
#define pc(a) printf("%c\n", a)
#define ps(a) printf("%s\n", a)
#define MOD 2018
#define eps 1e-7
#define LL long long
#define ULL unsigned long long
#define Pair pair<int, int>
#define mem(a, b) memset(a, b, sizeof(a))
#define _ ios_base::sync_with_stdio(0),cin.tie(0)
//freopen("1.txt", "r", stdin);
using namespace std;
const int maxn = , INF = 0x7fffffff;
int n, m, s, t;
vector<int> f, g;
struct edge
{
int u, v;
}Edge[maxn];
int head[maxn], cur[maxn], vis[maxn], d[maxn], cnt, nex[maxn << ];
int ans;
struct node
{
int u, v;
double c;
}Node[maxn << ]; void add_(int u, int v, double c)
{
Node[cnt].u = u;
Node[cnt].v = v;
Node[cnt].c = c;
nex[cnt] = head[u];
head[u] = cnt++;
} void add(int u, int v, double c)
{
add_(u, v, c);
add_(v, u, );
} bool bfs()
{
queue<int> Q;
mem(d, );
Q.push(s);
d[s] = ;
while(!Q.empty())
{
int u = Q.front(); Q.pop();
for(int i = head[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(!d[v] && Node[i].c > )
{
d[v] = d[u] + ;
Q.push(v);
if(v == t) return ;
}
}
}
return d[t] != ;
} double dfs(int u, double cap)
{
double ret = ;
if(u == t || abs(cap) < eps)
return cap;
for(int &i = cur[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(d[v] == d[u] + && Node[i].c > )
{
double V = dfs(v, min(cap, Node[i].c));
Node[i].c -= V;
Node[i ^ ].c += V;
ret += V;
cap -= V;
if(cap == ) break;
}
}
if(cap > ) d[u] = -;
return ret;
} double Dinic()
{
double ans = ;
while(bfs())
{
memcpy(cur, head, sizeof head);
ans += dfs(s, INF);
}
return ans;
} void build(double mid)
{
mem(head, -), cnt = ;
rap(i, , m)
{
add(s, i, );
add(i, m + Edge[i].u, INF);
add(i, m + Edge[i].v, INF);
}
rap(i, , n)
{
f.push_back(cnt);
// cout << mid << endl;
add(m + i, t, mid);
}
} void f_dfs(int u)
{
for(int i = head[u]; i != -; i = nex[i])
{
int v = Node[i].v;
if(!vis[v] && Node[i].c > eps)
{
vis[v] = , f_dfs(v);
if(v - m >= && v - m <= n) ans++;
}
}
} int main()
{
while(scanf("%d%d", &n, &m) != EOF)
{
ans = ;
f.clear();
g.clear();
if(m == )
{
cout << << endl;
cout << << endl;
continue;
}
mem(head, -);
cnt = ;
int u, v, sum = m;
f.clear();
s = , t = n + m + ;
rap(i, , m)
{
rd(Edge[i].u), rd(Edge[i].v);
}
double l = / (double) n, r = m;
while(r - l > (1.0 / n / n))
{
// mem(head, -1), cnt = 0;
// f.clear();
double mid = (r + l) / (double) ;
build(mid);
if(sum - Dinic() > eps) l = mid;
else r = mid;
}
f.clear();
build(l);
Dinic();
mem(vis, );
f_dfs(s);
cout << ans << endl;
for(int i = ; i <= n; i++)
if(vis[i + m])
cout << i << endl; } return ;
}