Pagini recente » Cod sursa (job #1970739) | Cod sursa (job #1402612) | Cod sursa (job #2161617) | Cod sursa (job #2555091) | Cod sursa (job #2396593)
#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<<' ';
}
}
}