Cod sursa(job #2396593)

Utilizator lflorin29Florin Laiu lflorin29 Data 3 aprilie 2019 17:23:07
Problema Componente tare conexe Scor 0
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 2.15 kb
#include <bits/stdc++.h>

using namespace std;

vector<int>reach(const vector<vector<int>>&dag, const vector<int>&topdag) {
  vector<int>rez(dag.size(), 1);
  vector<int>poz(topdag.size());
  assert(dag.size() == topdag.size());
  for(int i = 0; i < (int)topdag.size(); ++i)
    poz[topdag[i]] = i;
  for(int i : topdag) {
    if(!dag[i].empty()) {
      int next = dag[i][0];
      for(int j : dag[i])
        if(poz[j] < poz[next])
          next = j;
      rez[next] += rez[i];
    }
  }
  return rez;
}

int main() {
  ifstream cin("drumuri5.in");
  ofstream cout("drumuri5.out");

  int n, m;
  cin >> n >> m;
  vector<vector<int>>g(n);
  vector<int>low(n, -1), tin(n, 0), scc_id(n), stk;
  vector<bool>on_stk(n);
  int tmr = 0, cntScc = 0;
  for(int i = 0, u, v; i < m; ++i) {
    cin >> u >> v;
    g[u - 1].push_back(v - 1);
  }
  function<void(int)>get_sccs = [&] (int u) {
    stk.push_back(u);
    tin[u] = tmr++, low[u] = tin[u];
    on_stk[u] = true;
    for(int v : g[u]) {
      if(low[v] == -1) {
        get_sccs(v);
        low[u] = min(low[u], low[v]);
      } else if(on_stk[v])
        low[u] = min(low[u], tin[v]);

    }
    if(low[u] == tin[u]) {
      int node = -1;
      do {
        node = stk.back(), stk.pop_back();
        scc_id[node] = cntScc;
        on_stk[node] = false;
      } while(node != u);
      ++cntScc;
    }
  };

  for(int i = 0; i < n; ++i) if(low[i] == -1)
      get_sccs(i);
  vector<int>topdag;
  vector<vector<int>>dag(cntScc), revdag(cntScc);
  for(int i = cntScc - 1; i >= 0; --i) topdag.push_back(i);
  for(int i = 0; i < n; ++i) {
    for(int j : g[i]) {
      int u = scc_id[i], v = scc_id[j];
      if(u != v) {

        dag[u].push_back(v);
        revdag[v].push_back(u);
      }
    }
  }

  vector<int>before = reach(dag, topdag);
  reverse(topdag.begin(), topdag.end());
  vector<int>after = reach(revdag, topdag);

  int good = 0;
  for(int i = 0; i < n; ++i) {
    int where = scc_id[i];
    if(before[where] + after[where] == cntScc + 1) {
      ++good;
    }
  }
  cout << good << '\n';
   for(int i = 0; i < n; ++i) {
    int where = scc_id[i];
    if(before[where] + after[where] == cntScc + 1) {
      cout<<i+1<<' ';
    }
  }
}