AOJ2647.cpp

#include <bits/stdc++.h>

#define REP(i,n) for(int i=0;i<(int)(n);i++)
#define ALL(x) (x).begin(),(x).end()

using namespace std;

typedef int Weight;
Weight INF = 1000000000;
struct Edge{ int src, dest; Weight weight; };

typedef vector<Edge> Edges;
typedef vector<Edges> Graph;
typedef vector<Weight> Array;

void add_edge(Graph &g, int src, int dest, Weight weight) {
  g[src].push_back((Edge){src, dest, weight});
}

void bfs01(Graph &g, vector<int> &d, int s) {
  d.assign(g.size(), INF);
  d[s] = 0;
  typedef pair<Weight,int> P;
  deque<P> que;
  que.push_back(P(0, s));
  while (!que.empty()) {
    P top = que.front(); que.pop_front();
    Weight dist = top.first; int v = top.second;
    if (d[v] < dist) continue;
    REP(i, g[v].size()) {
      Edge e = g[v][i];
      if (d[e.dest] > d[v] + e.weight) {
        d[e.dest] = d[v] + e.weight;
        if (e.weight) que.push_back(P(d[e.dest], e.dest));
        else que.push_front(P(d[e.dest], e.dest));
      }
    }
  }
}

#define MAX_V 1024

vector<int> g[MAX_V], rg[MAX_V], vs;
bool used[MAX_V];
int cmp[MAX_V];

void add_edge(int from, int to) {
  g[from].push_back(to);
  rg[to].push_back(from);
}

void dfs(int v) {
  used[v] = true;
  for (int i : g[v]) if (!used[i]) dfs(i);
  vs.push_back(v);
}

void rdfs(int v, int k) {
  used[v] = true; cmp[v] = k;
  for (int i : rg[v]) if (!used[i]) rdfs(i, k);
}

int scc(int V) {
  memset(used, 0, sizeof(used));
  vs.clear();
  REP(v, V) if (!used[v]) dfs(v);
  memset(used, 0, sizeof(used));
  reverse(ALL(vs));
  int k = 0;
  for (int i : vs) if (!used[i]) rdfs(i, k++);
  return k;
}

void clearScc() {
  REP(i,MAX_V) g[i].clear();
  REP(i,MAX_V) rg[i].clear();
}

Weight MinimumArborescence(const Graph &g, int root) {
  const int n = g.size();
  Weight res = 0;
  vector<Weight> c(n, INF);
  vector<int> p(n, -1);
  for (int from = 0; from < n; from++) {
    for (Edge e : g[from]) {
      if (e.dest == from) continue;
      if (e.weight < c[e.dest]) p[e.dest] = from, c[e.dest] = e.weight;
      c[e.dest] = min(c[e.dest], e.weight);
    }
  }
  Graph ng(n);
  clearScc();
  for (int i = 0; i < n; i++) {
    if (i == root) continue;
    if (p[i] == -1) return INF;
    ng[p[i]].push_back((Edge){p[i], i, 0});
    add_edge(p[i], i);
    res += c[i];
  }
  int V = scc(n);
  vector<vector<int>> connect(V);
  REP(i,n) connect[cmp[i]].push_back(i);
  int m = connect.size();
  if (m == n) return res;
  vector<int> mapto(n, -1);
  vector<int> cycle(n, 0);
  res = 0;
  REP(i,m) {
    REP(j,connect[i].size()) {
      mapto[connect[i][j]] = i;
      if (connect[i].size() != 1)
        cycle[connect[i][j]] = 1, res += c[connect[i][j]];
    }
  }
  ng = Graph(m);
  for (int from = 0; from < n; from++) {
    for (Edge e : g[from]) {
      Weight cost = e.weight;
      if (e.dest == root || mapto[from] == mapto[e.dest]) continue;
      if (cycle[e.dest]) cost -= c[e.dest];
      ng[mapto[from]].push_back((Edge){mapto[from], mapto[e.dest], cost});
    }
  }
  return min(INF, res + MinimumArborescence(ng, mapto[root]));
}

int main() {
  int N, M;
  cin >> N >> M;
  Graph g1(N);
  vector<int> deg(N);
  REP(i,M) {
    int a, b;
    cin >> a >> b;
    add_edge(g1, a, b, 0);
    add_edge(g1, b, a, 1);
    ++deg[b];
  }
  vector<int> mapto;
  REP(i,N)
    if (deg[i] == 0) mapto.push_back(i);
  int V = mapto.size();
  Graph g2(V);
  REP(i,V) {
    Array dist;
    bfs01(g1, dist, mapto[i]);
    REP(j,V) add_edge(g2, i, j, dist[mapto[j]]);
  }
  vector<int> costs;
  REP(i,V) costs.push_back(MinimumArborescence(g2, i));
  int min_cost = INF;
  REP(i,V) min_cost = min(min_cost, costs[i]);
  vector<int> res;
  REP(i,V) if (costs[i] == min_cost) res.push_back(i);
  cout << res.size() << " " << min_cost << endl;
  REP(i,res.size()) {
    if (i > 0) cout << " ";
    cout << mapto[res[i]];
  }
  cout << endl;
  return 0;
}