Pagini recente » Cod sursa (job #864295) | Cod sursa (job #1174665) | Cod sursa (job #858781) | Cod sursa (job #327339) | Cod sursa (job #2583118)
#include <bits/stdc++.h>
using namespace std;
ifstream fin("drumuri5.in");
ofstream fout("drumuri5.out");
int n, m, sol, cnt, sum, nr, sz, l;
int head[150005], to[150005];
vector<int> graph[150005], newG[150005], nodes, new_node, op[150005];
stack<int> stk;
pair<int, int> p[150005];
bitset<150005> check, done, inS;
void connected(int now);
int main()
{
fin >> n >> m;
while(m--){
int x, y;
fin >> x >> y;
graph[x].push_back(y);
}
for(int i = 1; i <= n; ++i) head[i] = i;
for(int i = 1; i <= n; ++i){
if(!check[i]){
connected(i);
}
}
for(int i = 1; i <= n; ++i){
if(i == head[i]) ++cnt;
for(auto next:graph[i]){
if(head[i] == head[next]) continue;
newG[head[i]].push_back(head[next]);
op[head[next]].push_back(head[i]);
++to[head[next]];
}
}
for(int i = 1; i <= n; ++i){
if(!to[i] && head[i] == i)
nodes.push_back(i);
check[i] = false;
}
sz = nr = nodes.size();
while(sz){
if(nr == 1)
check[nodes[0]] = true;
for(int i = 0; i < sz; ++i){
for(auto next:newG[nodes[i]]){
--to[next];
if(!to[next])
new_node.push_back(next);
}
}
nr += new_node.size();
sz = new_node.size();
for(int i = 0; i < sz; ++i){
for(auto next:op[new_node[i]]){
if(!done[next]){
done[next] = true;
--nr;
}
}
}
nodes.clear();
nodes = new_node;
new_node.clear();
sz = nodes.size();
}
for(int i = 1; i <= n; ++i){
if(check[head[i]] == true)
++sol;
}
fout << sol << "\n";
for(int i = 1; i <= n; ++i){
if(check[head[i]] == true)
fout << i << " ";
}
return 0;
}
void connected(int now){
check[now] = true;
p[now] = {++l, l};
stk.push(now);
inS[now] = true;
for(auto next:graph[now]){
if(!check[next]){
connected(next);
p[now].second = min(p[now].second, p[next].second);
}
else if(inS[next]){
p[now].second = min(p[now].second, p[next].first);
}
}
if(p[now].first == p[now].second){
while(stk.top() != now){
head[stk.top()] = now;
inS[stk.top()] = false;
stk.pop();
}
head[stk.top()] = now;
inS[stk.top()] = false;
stk.pop();
}
}